CF1801D

CF1801D
题目大意：$n$ 个顶点，$m$ 条边的图。你一开始在起点 1，拥有 $P$ 枚硬币，通过每条 $(i,j)$ 边都需要花费一定的硬币 $s(i,j)$。但你在每个城市 $i$ 都可以打工赚硬币 $w_i$（可以多次打工）。请问从 1 到 $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$ （$i$ 是 $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. 打工次数。原方案的打工次数 = 子方案 { 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$ 到 $n$ 的打工次数。由于，原方案要求打工次数最少。因此，子方案的打工次数也应该越少越好。
2. 硬币数量。原方案的剩余的硬币数量 = 子方案 { 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$ 到 $n$ 的打工次数 * $w_i$ - $s(i,n)$。由于，并不知道原方案剩余多少硬币、$i$ 到 $n$ 的打工次数打了多少次工，导致我们无法知道子方案剩余的硬币数量。
3. 目的地。子方案目的地变为了 $i$。

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

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

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

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

• 令 $i$ 到 $n$ 的打工次数为 $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$ * max ⁡ { w } \max\{w\} max{w} - $s(i,n)$。

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

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

#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)$

#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;
}