PTA A_1087 All Roads Lead to Rome

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805379664297984

解：
迪杰斯特拉 + DFS（模板）

1. #include <iostream>
   
2. #include <climits>
   
3. #include <cstring>
   
4. #include <vector>
   
5. #include <map>
   
6. #include <algorithm>
   
7. 
   
8. using namespace std;
   
9. 
   
10. const int maxn = 210;
    
11. 
    
12. int n, k;
    
13. int d[maxn];
    
14. int pw[maxn];
    
15. bool vis[maxn];
    
16. int G[maxn][maxn];
    
17. vector<int> pre[maxn];
    
18. map<string, int> s2n;
    
19. map<int, string> n2s;
    
20. 
    
21. void DJS(void)
    
22. {
    
23.     fill(d, d + maxn, INT_MAX);
    
24.     memset(vis, false, sizeof(vis));
    
25. 
    
26.     d[0] = 0;
    
27. 
    
28.     for (int i = 0; i < n; i++)
    
29.     {
    
30.         int u  = -1, min = INT_MAX;
    
31. 
    
32.         for (int j = 0; j <= n; j++)
    
33.             if (!vis[j] && d[j] < min) min = d[u = j];
    
34. 
    
35.         if (u == -1) return;
    
36. 
    
37.         vis[u] = true;
    
38. 
    
39.         for (int v = 0; v <= n; v++)
    
40.         {
    
41.             if (vis[v] || G[u][v] == INT_MAX) continue;
    
42. 
    
43.             if (G[u][v] + d[u] < d[v])
    
44.             {
    
45.                 d[v] = G[u][v] + d[u];
    
46.                 pre[v].clear();
    
47.                 pre[v].push_back(u);
    
48.             }
    
49.             else if (G[u][v] + d[u] == d[v])
    
50.                 pre[v].push_back(u);
    
51.         }
    
52.     }
    
53. }
    
54. 
    
55. vector<int> path, temp_path;
    
56. int opt_w = -1;
    
57. int routes = 0;
    
58. 
    
59. void DFS(int id)
    
60. {
    
61.     if (!id)
    
62.     {
    
63.         int happy = 0;
    
64. 
    
65.         routes++;
    
66. 
    
67.         for (int i = temp_path.size() - 1; i >= 0; i--)
    
68.             happy += pw[temp_path[i]];
    
69. 
    
70.         if (happy > opt_w)
    
71.         {
    
72.             path = temp_path;
    
73.             opt_w = happy;
    
74.         }
    
75.     }
    
76. 
    
77.     temp_path.push_back(id);
    
78.    
    
79.     for (int i = 0; i < pre[id].size(); i++)
    
80.         DFS(pre[id][i]);
    
81. 
    
82.     temp_path.pop_back();
    
83. }
    
84. 
    
85. int main(void)
    
86. {
    
87.     // freopen("input.txt", "r", stdin);
    
88.     string s;
    
89.     cin >> n >> k >> s;
    
90. 
    
91.     n2s[0] = s;
    
92.     s2n[s] = 0;
    
93.         
    
94.     for (int i = 1; i < n; i++)
    
95.     {
    
96.         cin >> s >> pw[i];
    
97. 
    
98.         n2s[i] = s;
    
99.         s2n[s] = i;
    
100.     }
     
101. 
     
102.     fill(G[0], G[0] + maxn * maxn, INT_MAX);
     
103.    
     
104.     while (k--)
     
105.     {
     
106.         string s1, s2;
     
107.         int cost;
     
108. 
     
109.         cin >> s1 >> s2 >> cost;
     
110. 
     
111.         int a = s2n[s1], b = s2n[s2];
     
112. 
     
113.         G[a][b] = G[b][a] = cost;
     
114.     }
     
115. 
     
116.     DJS();
     
117.     DFS(s2n["ROM"]);
     
118. 
     
119.     cout << routes << " " << d[s2n["ROM"]] << " " << opt_w << " " << opt_w / path.size() << endl;
     
120. 
     
121.     cout << n2s[0];
     
122.     for (int i = path.size() - 1; i >= 0; i--)
     
123.         cout << "->" << n2s[path[i]];
     
124.         
     
125.     return 0;
     
126. }

复制代码