PTA A_1030 Travel Plan

798236606

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

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

1. #include <cstdio>
   
2. #include <climits>
   
3. #include <vector>
   
4. #include <algorithm>
   
5. 
   
6. using namespace std;
   
7. 
   
8. const int maxn = 510;
   
9. 
   
10. int n, m, c1, c2;
    
11. int G[maxn][maxn];
    
12. int cost[maxn][maxn];
    
13. int d[maxn];//存放最短路径长度
    
14. bool vis[maxn];//是否访问过
    
15. vector<int> pre[maxn];//存放顶点在最短路径中的前驱
    
16. 
    
17. void DJS(int s)
    
18. {
    
19.     fill(d, d + n, INT_MAX);
    
20.     d[s] = 0;
    
21. 
    
22.     for (int i = 0; i < n; i++)
    
23.     {   
    
24.         int u = -1, min = INT_MAX;
    
25. 
    
26.         for (int i = 0; i < n; i++)//查找未被访问过且距离最短的顶点
    
27.             if (!vis[i] && d[i] < min)  min = d[u = i];
    
28. 
    
29.         if (u == -1) return;//如果剩下的顶点与源点不通，返回
    
30. 
    
31.         vis[u] = true;
    
32. 
    
33.         for (int v = 0; v < n; v++)
    
34.         {
    
35.             if (vis[v] || G[u][v] == INT_MAX) continue;
    
36. 
    
37.             int t = d[u] + G[u][v];
    
38. 
    
39.             if (t < d[v])
    
40.             {
    
41.                 d[v] = t;
    
42.                 pre[v].clear();
    
43.                 pre[v].push_back(u);
    
44.             }  
    
45.             else if (t == d[v])
    
46.                 pre[v].push_back(u);
    
47.         }
    
48.     }
    
49. }
    
50. 
    
51. int opt_cost = INT_MAX;//存放最少花费
    
52. vector<int> path, temp_path;
    
53. 
    
54. void DFS(int v)
    
55. {
    
56.     if (v == c1)//递归边界，如果遍历到起点
    
57.     {
    
58.         temp_path.push_back(v);
    
59. 
    
60.         int val = 0;
    
61.         for (int i = temp_path.size() - 1; i > 0; i--)
    
62.             val += cost[temp_path[i]][temp_path[i - 1]];
    
63. 
    
64.         if (val < opt_cost)
    
65.         {
    
66.             opt_cost = val;
    
67.             path = temp_path;
    
68.         }
    
69. 
    
70.         temp_path.pop_back();
    
71. 
    
72.         return;
    
73.     }
    
74. 
    
75.     temp_path.push_back(v);
    
76. 
    
77.     for (int i = 0; i < pre[v].size(); i++)
    
78.         DFS(pre[v][i]);
    
79. 
    
80.     temp_path.pop_back();
    
81. }
    
82. 
    
83. int main(void)
    
84. {
    
85.     scanf("%d %d %d %d", &n, &m, &c1, &c2);
    
86.    
    
87.     fill(G[0], G[0] + maxn * maxn, INT_MAX);
    
88.    
    
89.     while (m--)
    
90.     {
    
91.         int a, b, l, c;
    
92.         scanf("%d %d %d %d", &a, &b, &l, &c);
    
93. 
    
94.         G[a][b] = G[b][a] = l;
    
95.         cost[a][b] = cost[b][a] = c;
    
96.     }
    
97. 
    
98.     DJS(c1);
    
99.     DFS(c2);
    
100. 
     
101.     for (int i = path.size() - 1; i >= 0; i--)
     
102.         printf("%d ", path[i]);
     
103. 
     
104.     printf("%d %d", d[c2], opt_cost);
     
105. 
     
106.     return 0;
     
107. }

复制代码