21天梯赛 森森旅游

两类不同类型的路径最值问题 考虑正反跑最短

#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)  // 需要排除不能到的情况，防止加入集合得到溢出后的错误答案

            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;

}