1087 all roads lead to Rome (30 points)

The shortest path with multiple conditions , The data range is very small , Write a plain version directly .

With two map Save name corresponding number , Name corresponding to number

See the code

#include <iostream>
#include <unordered_map>
#include <cstring>
using namespace std;
const int N = 300;
int g[N][N],dis[N],disha[N],ha[N],path[N],cnt[N],res[N],n,m;
bool st[N];
string start,en = "ROM";
unordered_map<string,int>mp;
unordered_map<int,string>idx;
void dijkstra()
{
	memset(dis,0x3f,sizeof dis);
	dis[mp[start]] = 0;
	res[mp[start]] = 1;
	for(int i = 0; i < n; i ++)
	{
		int u = -1;
		for(int j = 1; j <= n; j ++)
		{
			if(!st[j] && (u == -1 || dis[u] > dis[j])) u = j;
		}  
		st[u] = true;
		for(int j = 1; j <= n; j ++)
		{
			if(!st[j] && dis[j] > dis[u] + g[u][j])
			{
				dis[j] = dis[u] + g[u][j];//  shortest path  
				disha[j] =disha[u] + ha[j];// Happiness  
				cnt[j] = cnt[u] + 1;//  Path points  
				res[j] = res[u];// Number of shortest circuits  
				path[j] = u;// route  
			}
			else if(dis[j] == dis[u] + g[u][j])
			{   
				res[j] += res[u];
				if(disha[j] < disha[u] + ha[j])
				{
					disha[j] = disha[u] + ha[j];
					cnt[j] = cnt[u] + 1;
 					path[j] = u;
				}
				else if(disha[j] == disha[u] + ha[j])
					if(cnt[j] > cnt[u] + 1)
					{
						cnt[j] = cnt[u] + 1;
						path[j] = u;
					}
			}
		}
	}
}
void dfs(int u)
{
	if(u == mp[start])
	{
		cout << idx[u];return ;
	}
	dfs(path[u]);
	cout << "->" << idx[u];
}
int main()
{
	cin >> n >> m >> start;
	memset(g,0x3f,sizeof g);
	mp[start] = 1;idx[1] = start;
	for(int i = 2; i <= n ; i ++)
	{
		string s;int x;
		cin >> s >> x;
		mp[s] = i;idx[i] = s;ha[i] = x;
	}
	for(int i = 0; i < m; i ++)
	{
		string a,b;int x;
		cin >> a >> b >> x;
		g[mp[a]][mp[b]] = g[mp[b]][mp[a]] = x;
	}
	dijkstra();
	cout << res[mp[en]] << ' ' << dis[mp[en]] << ' ' << disha[mp[en]] << ' ' << disha[mp[en]] / (cnt[mp[en]]) << endl;
	dfs(mp[en]);
	return 0;
 }