作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
输入格式：
输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。
第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。
输出格式：
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
1
2
3
4
5
6
7
| 4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2
|
输出样例:
思路：
本题在求解最短距离的同时需要求解另外三个信息：最短路径条数num[u]、最短路径上的最大点权w[u]之和、最短路径的前一个结点pre[i]。令w[u]表示从起点s到达顶点u可以得到的最大点权之和，初始为0；令num[u]表示从起点s到达顶点u的最短路径条数，初始化时只有num[s]=1,其余num[u]均为0。当判定成立时，则更新。最后递归打印路径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include<bits/stdc++.h>
using namespace std;
const int maxv = 505;
const int INF = 0x3f3f3f3f;
int N,M,S,D;
int weight[maxv],G[maxv][maxv],d[maxv],w[maxv],num[maxv],pre[maxv];
bool vis[maxv] = {false};
void printPath(int v){
if(v==S){
cout << v;
return;
}
printPath(pre[v]);
cout <<" "<< v;
}
void Dijkstra(int s){
fill(d,d+maxv,INF);
memset(num,0,sizeof(num));
memset(w,0,sizeof(w));
d[s] = 0;
w[s] = weight[s];
num[s] = 1;
for(int i=0;i<N;i++){
int u = -1,MIN = INF;
for(int j=0;j<N;j++){
if(vis[j]==false&&d[j]<MIN){
u = j;
MIN = d[j];
}
}
if(u==-1) return;
vis[u] = true;
for(int v=0;v<N;v++){
if(vis[v]==false&&G[u][v]!=INF){
if(d[u]+G[u][v]<d[v]){
d[v] = d[u]+G[u][v];
w[v] = w[u]+weight[v];
num[v] = num[u];
pre[v] = u;
}else if(d[u]+G[u][v]==d[v]){
if(w[u]+weight[v]>w[v]){
w[v] = w[u] + weight[v];
pre[v] = u;
}
num[v] += num[u];
}
}
}
}
}
int main(){
cin >> N >> M >> S >> D;
for(int i=0;i<N;i++){
cin >> weight[i];
}
int u,v;
fill(G[0],G[0]+maxv*maxv,INF);
for(int i=0;i<M;i++){
cin >> u >> v;
cin >> G[u][v];
G[v][u] = G[u][v];
}
Dijkstra(S);
cout << num[D] <<" "<< w[D] << endl;
printPath(D);
return 0;
}
|
