【CCCC】L2-001 紧急救援 (25分)，，Dijkstra标准模板（多路径，最大点权和路径打印）

problem

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

输入格式:
输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。

第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式:
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

输入样例:
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

• 给一张图，n个点，m条边，从s出发到d。有点权和边权。
• 求最短路径条数（边权），打印点权和最大的路径。

solution

• DIjkstra+路径条数+最大点权+路径打印
• Dij的思想是根据是否确定最短路划分为两个点集，每次选取第二个集合中距离最近的加入最短路，并松弛其余边。松弛过程中，如果发现dis=dis+e(u,v)，则更新路径条数。同时比较哪一条的点权更大，用链表保留更大路径的上一个节点，用DFS打印路径。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 510;
const int inf = 99999999;

int n, m, c1, c2;
int e[maxn][maxn], w[maxn];
void Input(){
	cin>>n>>m>>c1>>c2;
	for(int i = 0; i < n; i++)
		cin>>w[i];
	memset(e,0x3f,sizeof(e));
	for(int i = 0; i < m; i++){
		int a, b, c;
		cin>>a>>b>>c;
		e[a][b] = e[b][a] = c;
	}
}

int dis[maxn], vis[maxn];//dist_lenght
int cnt[maxn];//dist_num
int weight[maxn]; //max_power
int pre[maxn];//pre_pass
void Solve(){
	memset(dis,0x3f,sizeof(dis));
	memset(pre,-1,sizeof(pre));
	dis[c1] = 0; 
	cnt[c1] = 1;
	weight[c1] = w[c1];
	for(int i = 0; i < n; i++){
		int u = -1, minn = inf;
		for(int j = 0; j < n; j++){
			if(!vis[j] && dis[j]<minn){
				minn = dis[j];
				u = j;
			}
		}
		if(u==-1)break;
		vis[u] = 1;
		for(int j = 0; j < n; j++){
			if(vis[j])continue;
			if(dis[j]>dis[u]+e[u][j]){
				dis[j] = dis[u]+e[u][j];
				cnt[j] = cnt[u];
				weight[j] = weight[u]+w[j];
				pre[j] = u;
			}else if(dis[j]==dis[u]+e[u][j]){
				cnt[j] += cnt[u];
				if(weight[u]+w[j]>weight[j]){
					weight[j] = weight[u]+w[j];
					pre[j] = u;
				}
			}
		}
	}
	//cout<<dis[c2]<<endl;
	cout<<cnt[c2]<<" "<<weight[c2]<<"\n";
}
void Print(int x){
	if(x==-1){
		return ;
	}else{
		Print(pre[x]);
		cout<<x<<" ";
	}
}

int main(){
	Input();
	Solve();
	Print(pre[c2]);
	cout<<c2<<"\n";
	return 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
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/108901155