共计 2839 个字符，预计需要花费 8 分钟才能阅读完成。
题目粗心:
有 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;
}
