L3-028 森森旅游 (30 分)-PAT 团体程序设计天梯赛 GPLT

好久没出去旅游啦!森森决定去 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≤a
​i′ ≤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

输出样例:
8
8
1

样例解释:
对于第一次汇率调整,森森可以沿着 1→2→4→6 的线路旅行,并在 2 号城市兑换旅游金;

对于第二次汇率调整,森森可以沿着 1→2→3→4→6 的线路旅行,并在 3 号城市兑换旅游金;

对于第三次汇率调整,森森可以沿着 1→3→5→6 的线路旅行,并在 1 号城市兑换旅游金。

分析:主体思路是,用Dijskra最短路算法分别算出:
1.使用现金从城市1出发,到达所有城市的最小花费(储存在cashD内)
2.使用旅游金从城市n出发,到达所有城市的最小花费(储存在voucherD内)
这样我们就能通过枚举中转点的方式,得到在第i个城市将现金换成旅游金的情况下所需要的现金总额~就是使用从城市1到达第i个城市所需要的最小现金数 + 从第i个城市到城市n所需要的最小旅游金数所转换成的现金数量,就可以得到在第i个城市兑换所需要的总现金费用,储存在tran[i]内~
huan[i]中储存第i个城市的汇率,cashE[i]和voucherE[i]中储分别储存使用现金和旅游金到达i可下一个城市的花费。最后将所有中转点所要用的花费储存在一个可以有重复值的multiset容器 minCost 中。最后在更新汇率时,将更新前花费从 minCost 中删除,并插入新值,然后输出 minCost 中的最小值就是答案啦~
注意:如果某点使用现金或旅游金不可达,那么该点的tran值则设置为0,在更新时改点也无需操作~

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版