CF1801D

CF1801D 题目大意： n n n 个顶点， m m m 条边的图。你一开始在起点 1，拥有 P P P 枚硬币，通过每条 ( i , j ) (i,j) (i,j) 边都需要花费一定的硬币 s ( i , j ) s(i,j) s(i,j)。但你在每个城市 i i i 都可以打工赚硬币 w i w_i wi​（可以多次打工）。请问从 1 到 n n n 的最少打工次数是多少次？

会有一个贪心的想法：去赚钱最多的城市打最少的工，然后一次性去到终点。但很快就能否决掉，在去赚硬币最多的城市的过程中可能要打很多次工。所以，只在一个城市打工的念头要彻底消除。而去哪打工？打多少次工最好？这是我们需要平衡的地方。因此，这应该是一个动态规划。

方法 1：

使用动态规划分析该问题，设最少打工次数的方案为： { 1 , a 1 , a 2 , . . . , a k , n } \{1,a_1,a_2,...,a_k,n\} {1,a1​,a2​,...,ak​,n}。 当 a k = i a_k=i ak​=i （ i i i 是 n n n 的邻接点）：方案变为 { 1 , a 1 , a 2 , . . . , a k − 1 , i , n } \{1,a_1,a_2,...,a_{k-1},i,n\} {1,a1​,a2​,...,ak−1​,i,n}。 方案的属性：

打工次数。原方案的打工次数 = 子方案 { 1 , a 1 , a 2 , . . . , a k − 1 , i } \{1,a_1,a_2,...,a_{k-1},i\} {1,a1​,a2​,...,ak−1​,i} 的打工次数 + i i i 到 n n n 的打工次数。由于，原方案要求打工次数最少。因此，子方案的打工次数也应该越少越好。硬币数量。原方案的剩余的硬币数量 = 子方案 { 1 , a 1 , a 2 , . . . , a k − 1 , i } \{1,a_1,a_2,...,a_{k-1},i\} {1,a1​,a2​,...,ak−1​,i} 剩余的硬币数量 + i i i 到 n n n 的打工次数 * w i w_i wi​ - s ( i , n ) s(i,n) s(i,n)。由于，并不知道原方案剩余多少硬币、 i i i 到 n n n 的打工次数打了多少次工，导致我们无法知道子方案剩余的硬币数量。目的地。子方案目的地变为了 i i i。

根据上述原因，我们的想法是：第一，需要给原问题多一维 剩余硬币 的状态。第二，在方案分析中，添加对打工次数的分类讨论。但是，由于剩余硬币可能是 0 ~ 1 0 9 10^9 109，不可能作为状态使用。对打工次数的分类讨论也无法实现，最多打多少次工呢？即使知道了，时间复杂度也无法通过题目。

此处就是题目较难的思维点：方案中，打工的地方，越往后打工的单价只会越来越高。因为，如果你后面打工的单价低，那还不如在前面先打好工呢。根据此，我们可得到，每一次向后走，用前面打工钱数最高的单价去打工，并且只需要尽量的能到达下一个地点即可。因此，打工次数无需枚举，是固定的。

i i i 到 n n n 的打工次数为：( s ( i , n ) s(i,n) s(i,n) - 子方案剩余的硬币数量) / max ⁡ { w } \max\{w\} max{w}。为了后续的打工次数少，子方案硬币能剩余的越多越好。

同时，打工次数被确定了后，每一次剩余的硬币数量也能被确定：

令 i i i 到 n n n 的打工次数为 h h h。原方案的剩余的硬币数量 = 子方案 { 1 , a 1 , a 2 , . . . , a k − 1 , i } \{1,a_1,a_2,...,a_{k-1},i\} {1,a1​,a2​,...,ak−1​,i} 剩余的硬币数量 + h h h * max ⁡ { w } \max\{w\} max{w} - s ( i , n ) s(i,n) s(i,n)。

所以，此时打工次数只剩下与 max ⁡ { w } \max\{w\} max{w} 也有关。而由于，一共只有 n n n 个物品。因此，我们可以增加一维状态用于表示经过的最高的可打工的地点。此时，子方案反映的问题是：从 1 到 i i i ，且打工的最高单价为 j j j，打工的最少次数是多少，同时剩余的硬币最多是多少？

又由于，这是在图论背景下的问题，我们只能选择贡献式递推去解决该问题，也就是使用 dijkstra 算法去递推。时间复杂度为 O ( n m log ⁡ n ) O(nm\log n) O(nmlogn)，如果把 dijkstra 变成朴素版本就可以到达 O ( n 3 ) O(n^3) O(n3)。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 810; int n,m,p; struct edge{ int to,cost; }; vector<edge>v[N]; struct node{ int now;ll time,coin;int maxn; bool operator < (const node &p)const{ if(time == p.time) return coin < p.coin; return time > p.time; } }; ll ans; int flag[N][N],w[N]; node dist[N][N]; void dij(){ for(int i = 0; i <= n; i++){ for(int j = 0; j <= n; j++){ flag[i][j] = 0; dist[i][j] = {0,(ll)1e18,0}; } } priority_queue<node>q; q.push({1,0,p,0}); dist[1][0] = {0,0,p,1}; while(q.size()){ node p = q.top(); q.pop(); int now = p.now; ll time = p.time,coin = p.coin; int maxn = p.maxn; // cout <<now << " " <<time <<" " <<coin << " " << maxn << "GGGG" << endl; if(now == n){ ans = min(ans,p.time); return; } if(flag[now][maxn]) continue; flag[now][maxn] = 1; for(int i = 0; i < v[now].size(); i++){ edge j = v[now][i]; int to = j.to;ll cost = j.cost; int newmaxn; if(w[maxn] < w[now]) newmaxn = now; else newmaxn = maxn; ll newtime,newcoin; if(coin >= cost) newtime = 0,newcoin = coin - cost; else{ newtime = (cost - coin + w[newmaxn] - 1) / w[newmaxn] ; newcoin = coin + newtime * w[newmaxn] - cost; } if(dist[to][newmaxn].time > time + newtime){ dist[to][newmaxn].coin = newcoin; dist[to][newmaxn].time = time + newtime; }else if(dist[to][newmaxn].time == time + newtime){ dist[to][newmaxn].coin = max(dist[to][newmaxn].coin,newcoin); } q.push({to,dist[to][newmaxn].time,dist[to][newmaxn].coin,newmaxn}); } } } int main(){ int t; cin >> t; while(t--){ cin >> n >> m >> p; for(int i = 1; i <= n; i++){ cin >> w[i]; v[i].clear(); } for(int i = 1; i <= m; i++){ int a,b,s; cin >> a >> b >> s; v[a].push_back({b,s}); } ans = 1e18; dij(); if(ans > 1e17) cout << -1 << endl; else cout << ans << endl; } return 0; } 方式 2

使用动态规划分析该问题，直接设最少打工次数的方案为： { 1 , a 1 , a 2 , . . . , a k , n } \{1,a_1,a_2,...,a_k,n\} {1,a1​,a2​,...,ak​,n}。 但是，这个方案中每个地方都打过工，忽略了未打工的地点。因为，上一个打工点直接通过最短路可以到达下一个打工点。这样做的好处是，我们不需要一维状态去表示最高打工单价了，每一次遍历到的点，就应该是最高打工单价。 下述代码使用了 floyd 去求解任意两个顶点之间的最短路。因此，时间复杂度为 O ( n 3 + m log ⁡ n ) O(n^3+m\log n) O(n3+mlogn)

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 810; int n,m,p; struct node{ int now;ll time,coin; bool operator < (const node &p)const{ if(time == p.time) return coin < p.coin; return time > p.time; } }; ll e[N][N]; void floyd(){ for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ e[i][j] = min(e[i][j],e[i][k] + e[k][j]); } } } } int flag[N],w[N]; node dist[N]; void dij(){ for(int i = 1; i <= n; i++){ flag[i] = 0; dist[i] = {0,(ll)1e18,0}; } priority_queue<node>q; q.push({1,0,p}); dist[1] = {0,0,p}; while(q.size()){ node p = q.top(); q.pop(); int now = p.now; ll time = p.time,coin = p.coin; //cout <<now << " " <<time <<" " <<coin << "GGGG" << endl; if(flag[now]) continue; flag[now] = 1; for(int i = 1; i <= n; i++){ int to = i;ll cost = e[now][i]; if(cost > 1e17) continue; ll newtime,newcoin; if(coin >= cost) newtime = 0,newcoin = coin - cost; else{ newtime = (cost - coin + w[now] - 1) / w[now]; newcoin = coin + newtime * w[now] - cost; } if(dist[to].time > dist[now].time + newtime){ dist[to].coin = newcoin; dist[to].time = dist[now].time + newtime; }else if(dist[to].time == dist[now].time + newtime){ dist[to].coin = max(dist[to].coin,newcoin); } q.push({to,dist[to].time,dist[to].coin}); } } } int main(){ int t; cin >> t; while(t--){ cin >> n >> m >> p; for(int i = 1; i <= n; i++){ cin >> w[i]; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ e[i][j] = 1e18; } e[i][i] = 0; } for(int i = 1; i <= m; i++){ int a,b,s; cin >> a >> b >> s; e[a][b] = min(e[a][b],(ll)s); } floyd(); dij(); if(dist[n].time > 1e17) cout << -1 << endl; else cout << dist[n].time << endl; } return 0; }