c/c++语言开发共享PAT甲级 1087. All Roads Lead to Rome (30) （dijkstra）

题目链接：传送门

思路：直接dijkstra即可，在过程中记录路径并转移各种情况，似乎先dijkstra记录路径再dfs比较好写。。但是我之前并没有想到
这种题因为dijkstra以贪心选择选取最近的点，只排除了不可能成为最短路的情况，有可能构成最短路的所有情况并没有被跳过，所以模拟即可

代码：

#include <bits/stdc++.h>  using namespace std;  const int maxn = 205;  struct node { 	int u , d; 	node(int a , int b):u(a) , d(b){} };  map <string , int> mp; vector <int> hap , res;  vector <string> vec; vector <node> g[maxn]; int cnt; int dist[maxn] ,  pre[maxn] , cs[maxn] , num[maxn] , cost[maxn]; bool vis[maxn];  int main() { 	int n , k; 	ios::sync_with_stdio(0); 	string u; 	cin >> n >> k >> u; 	vec.push_back(u); 	hap.push_back(0); 	mp[u] = cnt++; 	for(int i = 1 ; i < n ; i++) { 		string s; 		int t; 		cin >> s >> t; 		vec.push_back(s); 		hap.push_back(t); 		mp[s] = cnt++; 	} 	for(int i = 0 ; i < k ; i++) { 		string s , t; 		int cost; 		cin >> s >> t >> cost; 		int s1 = mp[s] , t1 = mp[t]; 		g[s1].push_back(node(t1 , cost)); 		g[t1].push_back(node(s1 , cost)); 	} 	memset(dist , 0x7f , sizeof(dist)); 	dist[0] = 0 , pre[0] = -1 , num[0] = 1 , cs[0] = 0 , cost[0] = 0;  	for(int i = 0 ; i < cnt - 1 ; i++) { 		int u = -1 , mm = 0x7f7f7f7f; 		for(int j = 0 ; j < cnt ; j++) { 			if(!vis[j] && mm > dist[j]) { 				u = j; 				mm = dist[j]; 			} 		} 		vis[u] = 1; 		for(int j = 0 ; j < g[u].size() ; j++) { 			int v = g[u][j].u; 			if(vis[v])continue; 			if(dist[v] > dist[u] + g[u][j].d) { 				num[v] = num[u]; 				pre[v] = u; 				cs[v] = cs[u] + 1; 				cost[v] = cost[u] + hap[v]; 				dist[v] = dist[u] + g[u][j].d; 			} 			else if(dist[v] == dist[u] + g[u][j].d) { 				num[v] += num[u]; 				int nhap = cost[u] + hap[v]; 				if(cost[v] < nhap) { 					pre[v] = u; 					cs[v] = cs[u] + 1; 					cost[v] = nhap; 				} 				else if(cost[v] == nhap && cs[v] > cs[u] + 1){ 					pre[v] = u; 					cs[v] = cs[u] + 1; 				} 			} 		} 	} 	int v = mp["ROM"]; 	cout << num[v] << " " << dist[v] <<" "<< cost[v] << " "<< cost[v] / cs[v] << "n";  	while(v != -1) { 		res.push_back(v); 	    v = pre[v]; 	} 	for(int i = res.size() - 1 ; i >= 0 ; i--) { 		if(i < res.size() - 1)cout << "->"; 		cout << vec[res[i]]; 	} 	cout << "n"; 	return 0; } 

c/c++开发分享PAT甲级 1087. All Roads Lead to Rome (30) （dijkstra）地址：https://blog.csdn.net/qq_39475280/article/details/107521040