主要是考虑怎么把字符串转换为数字
直接用两个map相互查找就行了
这种题就是见过了就知道怎么做
没什么技术含量

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int n,k;
string st;
const int maxn=210;
const int INF=1e9+5;
map<string,int> City2Index;
map<int,string> Index2City;
int weight[maxn]; 
int G[maxn][maxn]; //耗时 
int d[maxn]; //耗时最短
bool vis[maxn]={false}; 
int num=0; //最短路径有多少条 
vector<int> path,tempPath;
vector<int> pre[maxn];
void Dijkstra(int s){
	fill(d,d+maxn,INF);
	d[s]=0;
	for(int i=0;i<n;i++){ //n个顶点 
		int u=-1,Min=INF;  //每个中间点使源点能到达的最短路径的顶点 
		for(int j=0;j<n;j++){
			if(vis[j]==false && d[j] < Min){
				u = j;
				Min = d[j]; 
			}
		}
		if(u==-1) return;
		
		vis[u]=true;
		for(int v=0;v<n;v++){
			if(vis[v]==false && G[u][v]!=INF){
				if(G[u][v] + d[u] < d[v]){
					d[v]=G[u][v] + d[u];
					pre[v].clear();
					pre[v].push_back(u); //把u设为前驱节点 
				}else if(G[u][v] + d[u] == d[v]){
					pre[v].push_back(u); //直接加在v的后面，表示还有另一个前驱 
				} 
			}
		}
	}
	
}
int maxhappy=0;
double avehappy;
void DFS(int v) {
	if(v==0){
		tempPath.push_back(v);
		num++; 
		weight[0]=0;
		int tempmax=0;
		double tempave=0;
		for(int i=tempPath.size()-1;i>=0;i--){ //从0开始到终点 
			int id=tempPath[i];
			tempmax+=weight[id];
		}
		tempave= tempmax*1.0/(tempPath.size()-1);
		if(tempmax > maxhappy){
			maxhappy = tempmax;
			avehappy = tempave;
			path = tempPath;
		}else if(tempmax == maxhappy && tempave > avehappy){
			avehappy = tempave;
			path = tempPath;
		}
		tempPath.pop_back();
		return;	
	}
	tempPath.push_back(v);
	for(int j=0;j<pre[v].size();j++){
		DFS(pre[v][j]);
	}
	tempPath.pop_back();
}

int main(){
	cin>>n>>k>>st;
	string st1,st2,str;
	City2Index[st]=0;  //把城市转换为索引 
	Index2City[0]=st;  //把索引转换为城市 
	fill(G[0],G[0]+maxn*maxn,INF);
	for(int i=1;i<n;i++){   //点权幸福值 此处把所有城市都存下来了 
		cin>>str>>weight[i];
		City2Index[str]=i;
		Index2City[i]=str;
	}
	int cost;
	for(int i=0;i<k;i++){ //边权距离 
		cin>>st1>>st2;
		int c1=City2Index[st1],c2=City2Index[st2];  //先找出城市对应的索引 
		cin>>cost;
		G[c1][c2]=cost;
		G[c2][c1]=cost;  //无向图 
	}
	
	
	Dijkstra(0);
	int rom=City2Index["ROM"]; //终点 
	DFS(rom);
	printf("%d %d %d %d\n",num,d[rom],maxhappy,int(avehappy));
	for(int i=path.size()-1;i>=0;i--){
		cout<<Index2City[path[i]];
		if(i>0) cout<<"->";
	}
	cout<<endl;
	return 0;
}