PTA L3

PTA L3

【题目描述】
好久没出去旅游啦！
森森决定去Z省旅游一下。
Z省有 n n n座城市（从 1 ∼ n 1sim n 1∼n编号）以及 m m m条连接两座城市的有向旅行线路（例如自驾、长途汽车、火车、飞机、轮船等），每次经过一条旅行线路时都需要支付该线路的费用（但这个收费标准可能不止一种，例如车票跟机票一般不是一个价格）。
Z省为了鼓励大家在省内多逛逛，推出了旅游金计划：在 i i i号城市可以用 1 1 1元现金兑换 a i a_i ai​元旅游金（只要现金足够，可以无限次兑换）。
城市间的交通即可以使用现金支付路费，也可以用旅游金支付。
具体来说，当通过第 j j j条旅行线路时，可以用 c j c_j cj​元现金或 d j d_j dj​元旅游金支付路费。
注意：每次只能选择一种支付方式，不可同时使用现金和旅游金混合支付。
但对于不同的线路，旅客可以自由选择不同的支付方式。
森森决定从 1 1 1号城市出发，到 n n n号城市去。
他打算在出发前准备一些现金，并在途中的某个城市将剩余现金全部换成旅游金后继续旅游，直到到达 n n n号城市为止。
当然，他也可以选择在 1 1 1号城市就兑换旅游金，或全部使用现金完成旅程。
Z省政府会根据每个城市参与活动的情况调整汇率（即调整在某个城市 1 1 1元现金能换多少旅游金）。
现在你需要帮助森森计算一下，在每次调整之后最少需要携带多少现金才能完成他的旅程。

【输入格式】
输入在第一行给出三个整数 n , m , q n,m,q n,m,q，依次表示城市的数量、旅行线路的数量以及汇率调整的次数。
接下来 m m m行，每行给出四个整数 u , v , c , d u,v,c,d u,v,c,d，表示一条从 u u u号城市通向 v v v号城市的有向旅行线路。每次通过该线路需要支付 c c c元现金或 d d d元旅游金。数字间以空格分隔。输入保证从 1 1 1号城市出发，一定可以通过若干条线路到达 n n n号城市，但两城市间的旅行线路可能不止一条，对应不同的收费标准；也允许在城市内部游玩（即 u u u和 v v v相同）。
接下来的一行输入 n n n个整数 a 1 , a 2 , … , a n a_1,a_2,dots ,a_n a1​,a2​,…,an​，其中 a i a_i ai​表示一开始在 i i i号城市能用 1 1 1元现金兑换 a i a_i ai​个旅游金。数字间以空格分隔。
接下来 q q q行描述汇率的调整。第 i i i行输入两个整数 x i x_i xi​与 a i ′ a'_i ai′​，表示第 i i i次汇率调整后， x i x_i xi​号城市能用 1 1 1元现金兑换 a i ′ a'_i ai′​个旅游金，而其它城市旅游金汇率不变。请注意：每次汇率调整都是在上一次汇率调整的基础上进行的。

【输出格式】
对每一次汇率调整，在对应的一行中输出调整后森森至少需要准备多少现金，才能按他的计划从 1 1 1号城市旅行到 n n n号城市。
再次提醒：如果森森决定在途中的某个城市兑换旅游金，那么他必须将剩余现金全部、一次性兑换，剩下的旅途将完全使用旅游金支付。

【数据范围】
1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105
1 ≤ m ≤ 2 × 1 0 5 1≤m≤2×10^5 1≤m≤2×105
1 ≤ q ≤ 1 0 5 1≤q≤10^5 1≤q≤105
1 ≤ u , v ≤ n 1≤u,v≤n 1≤u,v≤n
1 ≤ c , d ≤ 1 0 9 1≤c,d≤10^9 1≤c,d≤109
1 ≤ a i ≤ 1 0 9 1≤a_i≤10^9 1≤ai​≤109
1 ≤ x i ≤ n 1≤x_i≤n 1≤xi​≤n
1 ≤ a i ′ ≤ 1 0 9 1≤a'_i≤10^9 1≤ai′​≤109

【输入样例】

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

【输出样例】

8
8
1

【样例解释】
对于第一次汇率调整，森森可以沿着 1 → 2 → 4 → 6 1→2→4→6 1→2→4→6的线路旅行，并在 2 2 2号城市兑换旅游金；
对于第二次汇率调整，森森可以沿着 1 → 2 → 3 → 4 → 6 1→2→3→4→6 1→2→3→4→6的线路旅行，并在 3 3 3号城市兑换旅游金；
对于第三次汇率调整，森森可以沿着 1 → 3 → 5 → 6 1→3→5→6 1→3→5→6的线路旅行，并在 1 1 1号城市兑换旅游金。

【分析】

首先我们使用Dijkstra算法求出两个数组 d i s 1 [ i ] , d i s 2 [ i ] dis1[i],dis2[i] dis1[i],dis2[i]，分别表示从 1 1 1号点走到 i i i号点所需的最少现金以及从 i i i号点走到 n n n号点所需的最少旅游金， d i s 2 dis2 dis2可以在反图上求出。

假如森森在 p p p号点将现金全部换成旅游金，那么他整个旅途所需的最少现金就为 d i s 1 [ p ] + ⌈ d i s 2 [ p ] / a [ p ] ⌉ dis1[p]+lceil dis2[p]/a[p]rceil dis1[p]+⌈dis2[p]/a[p]⌉。在修改汇率之前我们先枚举在每个点兑换旅游金的情况，将所有情况的花费存入 m u l t i s e t multiset multiset中，然后对于每次的汇率修改，我们先将 d i s 1 [ x ] + ⌈ d i s 2 [ x ] / a [ x ] ⌉ dis1[x]+lceil dis2[x]/a[x]rceil dis1[x]+⌈dis2[x]/a[x]⌉从 m u l t i s e t multiset multiset移除，然后修改汇率 a [ x ] = a ′ a[x]=a' a[x]=a′，再将 d i s 1 [ x ] + ⌈ d i s 2 [ x ] / a [ x ] ⌉ dis1[x]+lceil dis2[x]/a[x]rceil dis1[x]+⌈dis2[x]/a[x]⌉存入 m u l t i s e t multiset multiset中，然后输出 m u l t i s e t multiset multiset中最小的值即可，也就是第一个元素。

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 100010, M = 400010;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int e[M], ne[M], d[M], h[N], rh[N], idx;
LL a[N], dis1[N], dis2[N];
bool st[N];
int n, m, q;void add(int h[], int u, int v, int w)
{e[idx] = v, d[idx] = w, ne[idx] = h[u], h[u] = idx++;
}void dijkstra(int h[], LL dis[], int s)
{memset(st, false, sizeof st);memset(dis, 0x3f, sizeof dis1);priority_queue<PLI, vector<PLI>, greater<PLI>> Q;Q.push({ 0, s });dis[s] = 0;while (Q.size()){auto t = Q.top().second;Q.pop();if (st[t]) continue;st[t] = true;for (int i = h[t]; ~i; i = ne[i])if (dis[t] + d[i] < dis[e[i]])dis[e[i]] = dis[t] + d[i], Q.push({ dis[e[i]], e[i] });}
}int main()
{scanf("%d%d%d", &n, &m, &q);memset(h, -1, sizeof h);memset(rh, -1, sizeof rh);while (m--){int u, v, c, d;scanf("%d%d%d%d", &u, &v, &c, &d);add(h, u, v, c), add(rh, v, u, d);}for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);dijkstra(h, dis1, 1);dijkstra(rh, dis2, n);multiset<LL> S;for (int i = 1; i <= n; i++)if (dis1[i] != INF && dis2[i] != INF)S.insert(dis1[i] + (dis2[i] + a[i] - 1) / a[i]);while (q--){int x, y;scanf("%d%d", &x, &y);if (dis1[x] != INF && dis2[x] != INF){S.erase(S.find(dis1[x] + (dis2[x] + a[x] - 1) / a[x]));a[x] = y;S.insert(dis1[x] + (dis2[x] + a[x] - 1) / a[x]);}printf("%lldn", *S.begin());}return 0;
}