题目链接

3468. 森森旅游

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

输入格式

输入在第一行给出三个整数 \(n, m\) 与 \(q\) ，依次表示城市的数量、旅行线路的数量以及汇率调整的次数。
接下来 \(m\) 行，每行给出四个整数 \(u, v, c\) 与 \(d\) ，表示一条从 \(u\) 号城市通向 \(v\) 号城市的有向旅行线路。每次通过 该线路需要支付 \(c\) 元现金或 \(d\) 元旅斿金。数字间以空格分隔。输入保证从 \(1\) 号城市出发，一定可以通过若干条线 路到达 \(n\) 号城市，但两城市间的旅行线路可能不止一条，对应不同的收费标准；也允许在城市内部游玩（即 \(u\) 和\(v\) 相同）。
接下来的一行输入 \(n\) 个整数 \(a_{1}, a_{2}, \cdots, a_{n}\) ，其中 \(a_{i}\) 表示一开始在 \(i\) 号城市能用 1 元现金兑换 \(a_{i}\) 个旅游金。数 字间以空格分隔。
接下来 \(q\) 行描述汇率的调整。第 \(i\) 行输入两个整数 \(x_{i}\) 与 \(a_{i}^{\prime}\) ，表示第 \(i\) 次汇率调整后， \(x_{i}\) 号城市能用 1 元现金兑 换 \(a_{i}^{\prime}\) 个旅游金，而其它城市旅游金汇率不变。请注意：每次汇率调整都是在上一次汇率调整的基础上进行的。

输出格式

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

数据范围

\(\begin{aligned} &1 \leq n \leq 10^{5} \\ &1 \leq m \leq 2 \times 10^{5} \\ &1 \leq q \leq 10^{5} \\ &1 \leq u, v \leq n \\ &1 \leq c, d \leq 10^{9} \\ &1 \leq a_{i} \leq 10^{9} \\ &1 \leq x_{i} \leq n \\ &1 \leq a_{i}^{\prime} \leq 10^{9} \end{aligned} \)

输入样例：

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\) 号城市兑换旅游金。

解题思路

dijkstra

假设在某个点 \(x\) 处兑换旅游金，则在 \(x\) 前用的都是现金，\(x\) 后用的都是旅游金，两者独立，即 \(x\) 前的最小值与 \(x\) 后的最小值互不影响，可以转换为单源最短路问题，设 \(d1[i]\) 为 \(1\) 到 \(i\) 的最短路，\(d2[i]\) 为 \(n\) 到 \(i\) 的最短路，其中求 \(d2[i]\) 可反向建边，最后在 \(x\) 处兑换旅游金所需的最少现金为 \(d1[x]+\left \lceil \frac{d2[x]}{a[x]} \right \rceil\)，最后更新答案可用set，注意到达不了的点不能放进set里

• 时间复杂度：\(O(mlogn)\)

代码

// Problem: 森森旅游
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/3471/
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include 
 
// #define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair PII;
typedef pair PLL;
 
template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5;
const LL inf=0x3f3f3f3f3f3f3f3f;
int n,m,q,a[N];
LL d1[N],d2[N];
bool v[N];
vector adj1[N],adj2[N];
set s;
void dijkstra(int s,LL d[N],vector adj[N])
{
	memset(v,0,sizeof v);
	for(int i=1;i<=n;i++)d[i]=inf;
	d[s]=0;
	priority_queue,greater> q;
	q.push({0,s});
	while(q.size())
	{
		int x=q.top().se;
		q.pop();
		if(v[x])continue;
		v[x]=true;
		for(auto [y,w]:adj[x])
		{
			if(d[y]>d[x]+w)
			{
				d[y]=d[x]+w;
				q.push({d[y],y});
			}
		}
	}
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++)
    {
    	int a,b,c,d;
    	scanf("%d%d%d%d",&a,&b,&c,&d);
    	if(a==b)continue;
    	adj1[a].pb({b,c});
    	adj2[b].pb({a,d});
    }
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    dijkstra(1,d1,adj1);
    dijkstra(n,d2,adj2);
    for(int i=1;i<=n;i++)
        if(d1[i]!=inf&&d2[i]!=inf)s.insert({d1[i]+(d2[i]+a[i]-1)/a[i],i});
    while(q--)
    {
    	int x,w;
    	scanf("%d%d",&x,&w);
    	if(d1[x]==inf||d2[x]==inf)
    	{
    	    	printf("%lld\n",s.begin()->fi);
    	    	continue;
    	}
    	auto p=s.lower_bound({d1[x]+(d2[x]+a[x]-1)/a[x],x});
    	s.erase(p);
    	a[x]=w;
    	s.insert({d1[x]+(d2[x]+a[x]-1)/a[x],x});
    	printf("%lld\n",s.begin()->fi);
    }
    return 0;
}