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

本文地址：https://blog.csdn.net/qq_39475280/article/details/107521040