PTA A_1018 Public Bike Management

798236606

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805489282433024

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

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

复制代码