L2-001 紧急救援最短路+dfs

L2-001 紧急救援（25 分)

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式:

输入第一行给出4个正整数

第二行给出

输出格式:

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从

输入样例:

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例:

2 60
0 1 3

此题可用最短路模板走一遍找到最短路， 然后dfs一遍找到有多条路，并且记录一下路径。

 1 #include <bits/stdc++.h>
 2 #define N 505
 3 #define inf 0x3f3f3f3f
 4 using namespace std;
 5 int n, m;
 6 struct Node{
 7     int to, value;
 8     friend bool operator<(const Node &a , const Node &b){
 9         return a.value > b.value;
10     }
11 };
12 vector<Node> v[N];
13 int vis[N];
14 int val[N];
15 int fa[N], num[N];
16 int ans = 0,way = 0,weight = 0,st = 0;
17 int dis[N];
18 int x, y, z, s, d;
19 void short_path(int x){
20     priority_queue<Node> q;
21     q.push({x,0});
22     while(!q.empty()){
23         Node node = q.top();
24          q.pop();
25          if(vis[node.to] == 1)
26             continue;
27         vis[node.to] = 1;
28         val[node.to] = min(val[node.to], node.value);
29         ans ++;
30         if(ans == n) break;
31         for(int i = 0; i < v[node.to].size(); i ++){
32             Node an = v[node.to][i];
33             if(vis[an.to] == 0){
34                 q.push({an.to, val[node.to]+an.value});
35             }
36         }
37     }
38 }
39 
40 void dfs(int x, int cnt, int nums, int step){
41     fa[step] = x;
42     if(cnt == ans && x == d){
43         way++;
44         if(weight < nums){
45             weight = nums;
46             st = step;
47             memcpy(dis, fa, sizeof(fa));
48         }
49     }
50     if(cnt > ans) return ;
51     for(int i = 0; i < v[x].size(); i++){
52         Node an = v[x][i];
53         if(vis[an.to])
54             continue;
55         vis[an.to] = 1;
56         dfs(an.to, an.value+cnt, nums+num[an.to], step + 1);
57         vis[an.to] = 0;
58     }
59 }
60 
61 int main(){
62     scanf("%d%d%d%d", &n, &m, &s, &d);
63     for(int i = 0; i < n; i++){
64         scanf("%d", &num[i]);
65     }
66     memset(vis, 0, sizeof(vis));
67     memset(val, inf, sizeof(val));
68        
69     for(int i = 0; i < m; i ++){
70         scanf("%d%d%d", &x, &y, &z);
71         v[x].push_back({y, z});
72         v[y].push_back({x, z});
73     }
74     short_path(s);
75     ans = val[d];
76     memset(vis, 0, sizeof(vis));
77     vis[s] = 1;
78     dfs(s, 0, num[s], 0);
79     cout<<way<<" "<<weight<<endl;
80     for(int i = 0; i <= st; i ++){
81         if(i == 0)
82             printf("%d", dis[i]);
83         else
84             printf(" %d", dis[i]);
85     }
86     printf("
");
87     return 0;
88 }

L2-001 紧急救援 最短路+dfs

输入格式:

输出格式:

输入样例:

输出样例:

L2-001 紧急救援最短路+dfs