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