题目粗心:
有N个城市，K条无向边,当初须要从某个给定的起始城市登程,返回名为"ROM"的城市，给出每条边所须要耗费的破费,求从起始城市登程,
达到城市ROM所须要的起码破费,并输入起码破费的门路。如果这样的门路有多条，则抉择门路上城市的幸福值之和最大的那条门路，如果门路依然不惟一，则抉择门路上城市的均匀幸福值最大的那条 。
算法思路:
此题也是典型的Dijkstra算法模板题目,咱们这里的最短门路变动为最小破费,不过实质都一样,仍然应用dis数组存储每一个点到终点的最短距离，咱们通过Dijkstra算法(只掂量第一标尺,
也就是只思考破费最短)取得终点到所有节点的最小破费,以及在此门路上的所有节点的所有前驱结点,而后应用DFS遍历前驱结点数组pre(实质上是一颗树),从起点递归拜访每个结点的前驱,当拜访到终点的时候,阐明取得了一条门路,保留在shortest中,而后计算以后门路上的幸福感之和happ，如果以后happy比全局的最大幸福感max_happiness更大,那么更新 max_happiness = happ;min_num = shortest.size()-1;result = shortest;(保留门路),如果一样大然而均匀幸福感(门路长度)比全局的均匀最大幸福感(门路长度)min_num更大,也更新min_num = shortest.size()-1;result = shortest;并且得累计最短门路条数road_num。因为题目没有给定顶点范畴，所以这里采纳cityToIndex和intToCity保留顶点和编号(手动赋值)的双向映射以便于遍历和输入。
留神点：
- 1、均匀幸福值的计算不包含终点,因为终点的幸福值默认没有,所以是除以以后门路的结点数目-1,仔细观察样例的输入后果就晓得了
提交后果：
AC代码：
#include<cstdio>#include<vector>#include<string>#include<iostream>#include<unordered_map>#include<algorithm>using namespace std;int N,K,start=0,e;// 总人数，边数，终点,起点 int happiness[300];// 点权 int cost[300][300];// 边权 int dis[300];// 每一个城市间隔终点的最短距离bool visited[300];// 拜访标记数组vector<int> pre[300];// 每一个结点的所有前驱 vector<int> shortest;//最短门路vector<int> result;// 最优门路unordered_map<string,int> cityToIndex;// 保留城市到编号的映射 unordered_map<int,string> intToCity;// 保留编号到城市的映射int max_happiness = 0;int min_num = 0x3fffffff;// 起码结点数目int road_num = 0;// 最短门路条数 void DFS(int s){ shortest.push_back(s); if(s==start){ ++road_num; // 达到终点 int c = 0; int happ = 0; for(int i=shortest.size()-1;i>=0;--i){ if(i>0){ c += cost[shortest[i]][shortest[i-1]]; } if(i!=shortest.size()-1){ // 终点没有权值 happ += happiness[shortest[i]]; } } if(max_happiness<happ){ max_happiness = happ; min_num = shortest.size()-1; result = shortest; }else if(max_happiness==happ&&min_num>result.size()){ min_num = shortest.size()-1; result = shortest; } shortest.pop_back(); return; } for(int i=0;i<pre[s].size();++i){ DFS(pre[s][i]); } shortest.pop_back();} void Dijkstra(){ // 初始化 fill(dis,dis+300,0x3fffffff); dis[start] = 0; // 循环N+1次 for(int i=0;i<N;++i){ // 首先从所有未拜访的点中找到间隔终点最小的点 int nearest,minDis=0x3fffffff; for(int j=0;j<N;++j){ if(!visited[j]&&minDis>dis[j]){ nearest = j; minDis = dis[j]; } } if(minDis==0x3fffffff) return ;// 没有找到，阐明其余点不再连通 // 优化借助nearest到其余未拜访的点的间隔 visited[nearest] = true; for(int j=0;j<N;++j){ if(!visited[j]&&cost[nearest][j]!=0){ if(dis[j]>dis[nearest]+cost[nearest][j]){ dis[j] = dis[nearest]+cost[nearest][j]; pre[j].clear(); pre[j].push_back(nearest); }else if(dis[j]==dis[nearest]+cost[nearest][j]){ pre[j].push_back(nearest); } } } } }int main(){ string s; cin>>N>>K>>s; cityToIndex[s] = start; intToCity[start] = s; for(int i=1;i<N;++i){ cin>>s>>happiness[i]; cityToIndex[s] = i; intToCity[i] = s; if(s=="ROM") e = i; } string a,b; int C; for(int i=0;i<K;++i){ cin>>a>>b>>C; int index_a = cityToIndex[a]; int index_b = cityToIndex[b]; cost[index_a][index_b] = cost[index_b][index_a] = C; } Dijkstra(); DFS(e); printf("%d %d %d %d\n",road_num,dis[e],max_happiness,max_happiness/min_num); for(int i=result.size()-1;i>=0;--i){ printf("%s",intToCity[result[i]].c_str()); if(i>0) printf("->"); } return 0;}