题目描述

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

输入格式

输入第一行给出 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

输出样例

1
2
2 60
0 1 3

思路

链式前向星存图 Dijkstra 算法求最短路的同时求收集最多的路径 每次记录父亲结点 最后递归输出路径即可，最主要的是路径个数的求法，我们可以找一个数组来记录到达每个结点的路径条数，当距离更新的时候，此结点的路径个数就等于上一个结点的路径个数，当距离相等时，到达此结点最短路径的个数应该加上 上一个结点的；

AC 代码

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
68
69
70
#include<bits/stdc++.h>
using namespace std;
const int fw=1e6+10;
using pii=pair<int,int>;//让pii等于pair类型
int e[fw],ne[fw],h[fw],w[fw],rs[fw],xb,n,m,s,d,bj[fw],jl[fw],zrs[fw],pre[fw],road[fw];
//e数组存边的终点，ne数组存下一个点的下标，h数组存头结点的下标，w数组存边的长度
//rs数组存每个城市的人数，xb存e数组用到了哪里，n,m,s,d与题目变量对应，bj数组标记该城市是否
//访问过，jl数组存该城市距离起点的最短距离，zrs数组存当前城市到起点收集到的人数
//pre数组存储该结点的父亲结点，road数组存储到达此结点的路径个数。
priority_queue<pii,vector<pii>,greater<pii>>q;//优先队列存储已经收到的结点；
void cr(int x,int y,int z){//链式前向星插入模板
	e[xb]=y;//记录终点
	w[xb]=z;//记录边的长度
	ne[xb]=h[x];//把此结点插入到x这个链表中
	h[x]=xb++;//插入到头部
}
void djstl(int x){
	bj[x]=1;//标记为已经访问
	for(int i=h[x];i!=-1;i=ne[i]){//遍历这个城市可以到达的城市
		int f=e[i];//获取点的编号
		if(jl[f]>jl[x]+w[i]){//如果经过中转距离更短就更新
			jl[f]=jl[x]+w[i];//更新距离
			road[f]=road[x];//路径个数等于上一个点的
			zrs[f]=zrs[x]+rs[f];//更新人数
			pre[f]=x;
			q.push({jl[f],f});//推入优先队列
		}
		else if(jl[f]==jl[x]+w[i]){//如果距离相同 如果能收集到的人数更多就更新
			road[f]+=road[x];
			if(zrs[f]<zrs[x]+rs[f]){
				zrs[f]=zrs[x]+rs[f];
				pre[f]=x;
			}
		}
	}
	while(q.size()){//寻找没访问过的点
		int t=q.top().second;
		q.pop();
		if(!bj[t]){
			djstl(t);//递归这个点
			break;
		}
	}
}
void dy(int x){//路径打印函数
	if(x==s)return;
	dy(pre[x]);
	cout<<" "<<x;
}
int main(){
	memset(h,-1,sizeof h);
	memset(jl,0x3f,sizeof jl);//把距离置为无穷大
	cin>>n>>m>>s>>d;//输入城市个数，路的条数，起点，终点
	for(int i=0;i<n;i++)cin>>rs[i];//输入每个城市的人数
	while(m--){//输入边的信息
		int a,b,c;
		cin>>a>>b>>c;
		cr(a,b,c);
		cr(b,a,c);
	}
	jl[s]=0;//初始化距离
	zrs[s]=rs[s];//初始化人数
	road[s]=1;
	q.push({0,s});//把起点推入队列
	djstl(s);//求最合适的路径
	cout<<road[d]<<" "<<zrs[d]<<endl;//输出路径个数
	cout<<s;//先输出起点
	dy(d);//打印路径
	return 0;
}