题目分析：
本题我有两种思路，一种是只依靠dijkstra算法，在dijkstra部分直接判断所有的情况，以局部最优解得到全局最优解，另一种是dijkstra + dfs，先计算出最短距离以及每个点的可能前驱点，然后用dfs搜索每一条道路对最优路径进行维护，并且第二种方法记录道路的方式比较巧妙值得学习掌握（在dfs部分用一条临时路径进行维护）
对于字符串如何以整数的形式存储到二维数组中，这里用的是map的方式，当然也可以通过字符串计算出hash值去索引，毕竟是三个大写字母的字符串
本题代码：
1 #include<iostream>
2 #include<string>
3 #include<cmath>
4 #include<map>
5 #include<string.h>
6 #include<vector>
7 #include<algorithm>
8 #include<stdio.h>
9 using namespace std;
10
11 const int M = 0x3f3f3f3f;
12 const int N = 205;
13 int mat[N][N];
14 int vis[N];
15 int dist[N];
16 int peo[N];
17 vector<int> pre[N];
18 vector<int> path, temppath;
19 map<string, int> mp1; //每个城市对应的id
20 map<int, string> mp2; //每个id对应的城市
21 int n, m, min_dist, max_kill, road_num;
22 string from, to;
23
24 int minn(){
25 int k = -1;
26 int Min = M;
27 for(int i = 1; i <= n; i++){
28 if(vis[i] == 0 && dist[i] < Min){
29 Min = dist[i];
30 k = i;
31 }
32 }
33 return k;
34 }
35
36 void dijkstra(){
37 max_kill = 0;
38 road_num = 0;
39 min_dist = 0;
40 memset(vis, 0, sizeof(vis));
41 memset(dist, M, sizeof(dist));
42 dist[1] = 0; //起点到自己距离为0
43 for(int i = 1; i <= n; i++){
44 int k = minn();
45 if(k == -1) break;
46 vis[k] = 1;
47 for(int j = 1; j <= n; j++){
48 if(vis[j] == 0 && dist[k] + mat[k][j] < dist[j]){
49 dist[j] = dist[k] + mat[k][j];
50 pre[j].clear();
51 pre[j].push_back(k);
52 }else if(vis[j] == 0 && dist[k] + mat[k][j] == dist[j]){
53 pre[j].push_back(k);
54 }
55 }
56 }
57 min_dist = dist[mp1[to]];
58 }
59
60 void dfs(int x){
61 temppath.push_back(x);
62 if(x == mp1[from]){
63 //现在需要找出同距离下点最多且杀敌最多
64 road_num++; //不论是点多的 少的 一样多的都算是同样距离的一条最短路径
65 int kill = 0;
66 for(int i = temppath.size()-1; i >= 0; i--){
67 int id = temppath[i];
68 kill += peo[id];
69 }
70 if(temppath.size() > path.size()){
71 path = temppath;
72 max_kill = kill;
73 }else if(temppath.size() == path.size()){
74 if(kill > max_kill){
75 max_kill = kill;
76 path = temppath;
77 }
78 }
79 temppath.pop_back();
80 return;
81 }
82 for(int i = 0; i < pre[x].size(); i++)
83 dfs(pre[x][i]);
84 temppath.pop_back();
85 }
86
87 int main(){
88 scanf("%d%d", &n, &m);
89 cin>>from>>to;
90 mp1[from] = 1;
91 mp2[1] = from;
92 for(int i = 2; i <= n; i++){
93 string s; int x;
94 cin>>s; scanf("%d", &x);
95 mp1[s] = i;
96 mp2[i] = s;
97 peo[mp1[s]] = x;
98 }
99 memset(mat, M, sizeof(mat));
100 for(int i = 1; i <= m; i++){
101 string s1, s2;
102 cin>>s1>>s2;
103 scanf("%d", &mat[mp1[s1]][mp1[s2]]);
104 mat[mp1[s2]][mp1[s1]] = mat[mp1[s1]][mp1[s2]];
105 }
106 dijkstra(); //计算出最短路径
107 dfs(mp1[to]); //计算最优路径
108 cout<<mp2[1];
109 for(int i = path.size()-2; i >= 0; i--) cout<<"->"<<mp2[path[i]]; //注意起始点已经输出了
110 printf("\n");
111 printf("%d %d %d\n", road_num, min_dist, max_kill);
112 return 0;
113 }