L3-1 森森旅游 (30 分)
好久没出去旅游啦！森森决定去 Z 省旅游一下。
Z 省有 n 座城市（从 1 到 n 编号）以及 m 条连接两座城市的有向旅行线路（例如自驾、长途汽车、火车、飞机、轮船等），每次经过一条旅行线路时都需要支付该线路的费用（但这个收费标准可能不止一种，例如车票跟机票一般不是一个价格）。
Z 省为了鼓励大家在省内多逛逛，推出了旅游金计划：在 i 号城市可以用 1 元现金兑换 ai 元旅游金（只要现金足够，可以无限次兑换）。城市间的交通即可以使用现金支付路费，也可以用旅游金支付。具体来说，当通过第 j 条旅行线路时，可以用 cj 元现金或 dj 元旅游金支付路费。注意： 每次只能选择一种支付方式，不可同时使用现金和旅游金混合支付。但对于不同的线路，旅客可以自由选择不同的支付方式。
森森决定从 1 号城市出发，到 n 号城市去。他打算在出发前准备一些现金，并在途中的某个城市将剩余现金 全部 换成旅游金后继续旅游，直到到达 n 号城市为止。当然，他也可以选择在 1 号城市就兑换旅游金，或全部使用现金完成旅程。
Z 省政府会根据每个城市参与活动的情况调整汇率（即调整在某个城市 1 元现金能换多少旅游金）。现在你需要帮助森森计算一下，在每次调整之后最少需要携带多少现金才能完成他的旅程。
输入格式:
输入在第一行给出三个整数 n，m 与 q（1≤n≤105，1≤m≤2×105，1≤q≤105），依次表示城市的数量、旅行线路的数量以及汇率调整的次数。
接下来 m 行，每行给出四个整数 u，v，c 与 d（1≤u,v≤n，1≤c,d≤109），表示一条从 u 号城市通向 v 号城市的有向旅行线路。每次通过该线路需要支付 c 元现金或 d 元旅游金。数字间以空格分隔。输入保证从 1 号城市出发，一定可以通过若干条线路到达 n 号城市，但两城市间的旅行线路可能不止一条，对应不同的收费标准；也允许在城市内部游玩（即 u 和 v 相同）。
接下来的一行输入 n 个整数 a1,a2,⋯,an（1≤ai≤109），其中 ai 表示一开始在 i 号城市能用 1 元现金兑换 ai 个旅游金。数字间以空格分隔。
接下来 q 行描述汇率的调整。第 i 行输入两个整数 xi 与 ai′（1≤xi≤n，1≤ai′≤109），表示第 i 次汇率调整后，xi 号城市能用 1 元现金兑换 ai′ 个旅游金，而其它城市旅游金汇率不变。请注意：每次汇率调整都是在上一次汇率调整的基础上进行的。
输出格式:
对每一次汇率调整，在对应的一行中输出调整后森森至少需要准备多少现金，才能按他的计划从 1 号城市旅行到 n 号城市。
再次提醒：如果森森决定在途中的某个城市兑换旅游金，那么他必须将剩余现金全部、一次性兑换，剩下的旅途将完全使用旅游金支付。
输入样例:
6 11 3 1 2 3 5 1 3 8 4 2 4 4 6 3 1 8 6 1 3 10 8 2 3 2 8 3 4 5 3 3 5 10 7 3 3 2 3 4 6 10 12 5 6 10 6 3 4 5 2 5 100 1 2 2 1 1 17
结尾无空行
输出样例:
1. 8 2. 8 3. 1
结尾无空行
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,int>PLL; const int N=100010,M=200010*2; const LL INF=0x3f3f3f3f3f3f3fll; int n,m,Q; int h1[N],h2[N],e[M],w[M],ne[M],idx; LL dist1[N],dist2[N]; bool st[N]; int ratio[N];//汇率 //带边权的加边函数 void add(int h[],int a,int b,int c)//添加一条边a->b，边权为c { e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++; } void dijkstar(int h[],LL dist[],int start) { memset(dist,0x3f,sizeof(dist1)); memset(st,0,sizeof(st)); dist[start]=0; priority_queue<PLL,vector<PLL>,greater<PLL>>heap; heap.push({0,start}); while(heap.size()) { auto t=heap.top(); heap.pop(); int ver=t.second; if(st[ver])continue; for(int i=h[ver];i!=-1;i=ne[i]) { int j=e[i]; if(dist[j]>dist[ver]+w[i]) { dist[j]=dist[ver]+w[i]; heap.push({dist[j],j}); } } } } int main(){ scanf("%d%d%d",&n,&m,&Q); memset(h1,-1,sizeof(h1));//清空邻接表表头 memset(h1,-1,sizeof(h1)); while(m--){//读入m条边 int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); add(h1,a,b,c);//从起点除发只用现金的距离最小值 add(h2,b,a,d);//（反向边）中点出发 } //读入汇率 for(int i=1;i<=n;i++)scanf("%d",&ratio[i]); dijkstar(h1,dist1,1); dijkstar(h2,dist2,n); multiset<LL>S; for(int i=1;i<=n;i++) if(dist1[i]!=INF&&dist2[i]!=INF) { S.insert(dist1[i]+(dist2[i]+ratio[i]-1)/ratio[i]); } while(Q--){ int a,b; scanf("%d%d",&a,&b); if(dist1[a]!=INF&&dist2[a]!=INF) { S.erase(S.find(dist1[a]+(dist2[a]+ratio[a]-1)/ratio[a])); ratio[a]=b; S.insert(dist1[a]+(dist2[a]+ratio[a]-1)/ratio[a]); } printf("%lld\n",*S.begin()); } return 0; }
样例解释:
对于第一次汇率调整，森森可以沿着 1→2→4→6 的线路旅行，并在 2 号城市兑换旅游金；
对于第二次汇率调整，森森可以沿着 1→2→3→4→6 的线路旅行，并在 3 号城市兑换旅游金；
对于第三次汇率调整，森森可以沿着 1→3→5→6 的线路旅行，并在 1 号城市兑换旅游金。
