PYA A_1003 Emergency

798236606

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

解：
最短路径

1.迪杰斯特拉

1. #include <cstdio>
   
2. #include <climits>
   
3. #include <algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. const int maxn = 510;
   
8. 
   
9. int n, m, c1, c2;
   
10. int G[maxn][maxn];
    
11. int men[maxn];//存放点权，即救援队数
    
12. int num[maxn];//存放到每个点的最短路径数
    
13. int w[maxn];//存放可聚集的队伍数
    
14. int v[maxn];//存放最短路径长度
    
15. bool vis[maxn];//是否访问过
    
16. 
    
17. void DJS(int s)
    
18. {
    
19.     fill(v, v + n, INT_MAX);
    
20.     fill(num, num + n, 0);
    
21.     fill(w , w + n, 0);
    
22.     v[s] = 0;
    
23.     w[s] = men[s];
    
24.     num[s] = 1;
    
25. 
    
26.     for (int i = 0; i < n; i++)
    
27.     {   
    
28.         int u = -1, min = INT_MAX;
    
29. 
    
30.         for (int i = 0; i < n; i++)//查找未被访问过且距离最短的顶点
    
31.             if (!vis[i] && v[i] < min)  min = v[u = i];
    
32. 
    
33.         if (u == -1) return;//如果剩下的顶点与源点不通，返回
    
34. 
    
35.         vis[u] = true;
    
36. 
    
37.         for (int j = 0; j < n; j++)
    
38.         {
    
39.             if (vis[j] || G[u][j] == INT_MAX) continue;
    
40. 
    
41.             int t = v[u] + G[u][j];
    
42. 
    
43.             if (t < v[j])
    
44.             {
    
45.                 v[j] = t;
    
46.                 num[j] = num[u];
    
47.                 w[j] = w[u] + men[j];
    
48.             }  
    
49.             else if (t == v[j])
    
50.             {
    
51.                 num[j] += num[u];
    
52. 
    
53.                 if (w[u] + men[j] > w[j]) w[j] = w[u] + men[j];
    
54.             }
    
55.         }
    
56.     }
    
57. }
    
58. 
    
59. int main(void)
    
60. {
    
61.     scanf("%d %d %d %d", &n, &m, &c1, &c2);
    
62. 
    
63.     fill(G[0], G[0] + maxn * maxn, INT_MAX);
    
64. 
    
65.     for (int i = 0; i < n; i++)
    
66.         scanf("%d", men + i);
    
67. 
    
68.     while (m--)
    
69.     {
    
70.         int a, b, l;
    
71. 
    
72.         scanf("%d %d %d", &a, &b, &l);
    
73. 
    
74.         G[a][b] = G[b][a] = l;
    
75.     }
    
76. 
    
77.     DJS(c1);
    
78. 
    
79.     printf("%d %d", num[c2], w[c2]);
    
80. 
    
81.     return 0;
    
82. }

复制代码

2.迪杰斯特拉 + 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 weight[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 num = 0;//存放最短路径条数
    
52. int opt_w = 0;//存放最大点权和
    
53. vector<int> path;
    
54. 
    
55. void DFS(int v)
    
56. {
    
57.     if (v == c1)//递归边界，如果遍历到起点
    
58.     {
    
59.         path.push_back(v);
    
60. 
    
61.         num++;
    
62. 
    
63.         int val = 0;
    
64.         for (int i = path.size() - 1; i >= 0; i--)
    
65.             val += weight[path[i]];
    
66. 
    
67.         if (val > opt_w) opt_w = val;
    
68. 
    
69.         path.pop_back();
    
70. 
    
71.         return;
    
72.     }
    
73. 
    
74.     path.push_back(v);
    
75. 
    
76.     for (int i = 0; i < pre[v].size(); i++)
    
77.         DFS(pre[v][i]);
    
78. 
    
79.     path.pop_back();
    
80. }
    
81. 
    
82. int main(void)
    
83. {
    
84.     scanf("%d %d %d %d", &n, &m, &c1, &c2);
    
85.    
    
86.     fill(G[0], G[0] + maxn * maxn, INT_MAX);
    
87. 
    
88.     for (int i = 0; i < n; i++)
    
89.         scanf("%d", weight + i);
    
90.    
    
91.     while (m--)
    
92.     {
    
93.         int a, b, l;
    
94.         scanf("%d %d %d", &a, &b, &l);
    
95. 
    
96.         G[a][b] = G[b][a] = l;
    
97.     }
    
98. 
    
99.     DJS(c1);
    
100.     DFS(c2);
     
101. 
     
102.     printf("%d %d", num, opt_w);
     
103. 
     
104.     return 0;
     
105. }

复制代码

3.BF算法

1. #include <cstdio>
   
2. #include <climits>
   
3. #include <cstring>
   
4. #include <vector>
   
5. #include <set>
   
6. #include <algorithm>
   
7. 
   
8. using namespace std;
   
9. 
   
10. const int maxn = 510;
    
11. 
    
12. typedef struct node{
    
13.     int id, dis;
    
14. 
    
15.     node (int _id, int _dis) : id(_id), dis(_dis) {};
    
16. }Node;
    
17. 
    
18. int n, m, c1, c2;
    
19. int weight[maxn];//存放点权，即救援队数
    
20. int num[maxn];//存放到每个点的最短路径数
    
21. int w[maxn];//存放可聚集的队伍数
    
22. int d[maxn];//存放最短路径长度
    
23. vector<Node> adj[maxn];//邻接表
    
24. set<int> pre[maxn];//存放顶点在最短路径中的前驱
    
25. 
    
26. void BF(int s)
    
27. {
    
28.     fill(d, d + n, INT_MAX);
    
29.     memset(w, 0, sizeof(w));
    
30.     memset(num, 0, sizeof(num));
    
31. 
    
32.     w[s] = weight[s];
    
33.     d[s] = 0;
    
34.     num[s] = 1;
    
35. 
    
36.     for (int i = 0; i < n - 1; i++)
    
37.     {
    
38.         for (int u = 0; u < n; u++)
    
39.         {
    
40.             if (d[u] == INT_MAX) continue;
    
41. 
    
42.             for (int v = 0; v < adj[u].size(); v++)
    
43.             {
    
44.                 int id = adj[u][v].id, dis = adj[u][v].dis;
    
45. 
    
46.                 if (dis + d[u] < d[id])
    
47.                 {
    
48.                     d[id] = dis + d[u];
    
49.                     num[id] = num[u];
    
50.                     w[id] = weight[id] + w[u];
    
51.                     pre[id].clear();
    
52.                     pre[id].insert(u);
    
53.                 }
    
54.                 else if (dis + d[u] == d[id])
    
55.                 {
    
56.                     if (weight[id] + w[u] > w[id])
    
57.                         w[id] = weight[id] + w[u];
    
58. 
    
59.                     num[id] = 0;
    
60.                     
    
61.                     pre[id].insert(u);
    
62.                     for (set<int>::iterator it = pre[id].begin(); it != pre[id].end(); ++it)
    
63.                         num[id] += num[*it];
    
64.                 }
    
65.             }
    
66.         }
    
67.     }
    
68. }
    
69. 
    
70. int main(void)
    
71. {
    
72.     // freopen("input.txt", "r", stdin);
    
73.     scanf("%d %d %d %d", &n, &m, &c1, &c2);
    
74. 
    
75.     for (int i = 0; i < n; i++)
    
76.         scanf("%d", weight + i);
    
77.    
    
78.     while (m--)
    
79.     {
    
80.         int a, b, l;
    
81.         scanf("%d %d %d", &a, &b, &l);
    
82. 
    
83.         adj[a].push_back(node(b, l));
    
84.         adj[b].push_back(node(a, l));
    
85.     }
    
86. 
    
87.     BF(c1);
    
88. 
    
89.     printf("%d %d", num[c2], w[c2]);
    
90. 
    
91.     return 0;
    
92. }

复制代码