兩類不同類型的路徑最值問題 考慮正反跑最短

#include <iostream>

#include <cstring>

#include <algorithm>

#include <set>

#include <queue>

#define x first

#define y second

#define int long long

using namespace std;

typedef pair<int, int> P;

const int N = 8e5+10,M = N,INF = 0x3f3f3f3f3f3f3f3f;

int n,m,q,ratio[N],d1[N],d2[N];

int h[N],e[N],ne[N],idx,w[N],rh[N];

bool st[N];

void add(int h[],int a,int b,int c){

? ? e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;

}

void dijkstra(int h[],int start,int dist[]){

? ? memset(dist,0x3f,sizeof d1);

? ? memset(st,0,sizeof st);

? ? priority_queue<P,vector<P>,greater<P>> heap;

? ? dist[start]=0;

? ? heap.push({0,start});

? ? while(heap.size()){

? ? ? ? auto t=heap.top();heap.pop();

? ? ? ? int u=t.y;

? ? ? ? if(st[u]) continue;

? ? ? ? st[u]=1;

? ? ? ? for(int i=h[u];~i;i=ne[i]){

? ? ? ? ? ? int v=e[i];

? ? ? ? ? ? if(dist[v]>dist[u]+w[i]){

? ? ? ? ? ? ? ? dist[v]=dist[u]+w[i];

? ? ? ? ? ? ? ? heap.push({dist[v],v});

? ? ? ? ? ? }

? ? ? ? }

? ? }

}

signed main(){

? ? ios::sync_with_stdio(false);

? ? memset(h,-1,sizeof h);

? ? memset(rh,-1,sizeof rh);

? ? cin>>n>>m>>q;

? ? while(m--){

? ? ? ? int u,v,c,d;

? ? ? ? cin>>u>>v>>c>>d;

? ? ? ? add(h,u,v,c),add(rh,v,u,d);

? ? }

? ? for(int i=1;i<=n;i++) cin>>ratio[i];

? ? dijkstra(h,1,d1);

? ? dijkstra(rh,n,d2);

? ? multiset<int> s;

? ? for(int i=1;i<=n;i++){

? ? ? ? if(d1[i]!=INF&&d2[i]!=INF)? // 需要排除不能到的情況，防止加入集合得到溢出后的錯(cuò)誤答案

? ? ? ? ? ? s.insert(d1[i]+(d2[i]+ratio[i]-1)/ratio[i]);

? ? }

? ? while(q--){

? ? ? ? int x,t;

? ? ? ? cin>>x>>t;

? ? ? ? if(d1[x]!=INF&&d2[x]!=INF){

? ? ? ? ? ? s.erase(s.find(d1[x]+(d2[x]+ratio[x]-1)/ratio[x]));

? ? ? ? ? ? ratio[x]=t;

? ? ? ? ? ? s.insert(d1[x]+(d2[x]+ratio[x]-1)/ratio[x]);

? ? ? ? }

? ? ? ? cout<<*s.begin()<<endl;

? ? }

? ? return 0;

}