L2-001 紧急救援

这道题就是在dijkstra的基础上增加了一些东西。
代码有参考别人，最后一步的处理很好。

#include <bits/stdc++.h>
using namespace std;
const int maxv = 0x7fffffff;
int edges[510][510];//从i到j的长度
int dist[510];//最短路径
bool check[510];//是否在集合之中
int num[510];//每个地点救援队的数量
int values[510];//到每个点救援队伍的数量
int cnt[510];//到每个点最短路的数量
int pre[510];//从哪里来的
int main() {
	int n,m,s,d;
	cin >> n>>m>>s>>d;
	for(int i=0; i<n; i++) cin>>num[i];
	for(int i=0; i<m; i++) {
		int a,b,c;
		cin>>a>>b>>c;
		edges[a][b]=c;
		edges[b][a]=c;
	}
	memset(dist,0x3f,sizeof(dist));
	memset(pre,-1,sizeof(pre));
	//起始点初始化
	dist[s]=0;
	values[s]=num[s];
	cnt[s]=1;
	for(int i=0; i<n; i++) {
		int minv=maxv,minx;
		for(int j=0; j<n; j++) { //找到最小的加入到集合中
			if(dist[j]<minv&&!check[j]) {
				minv=dist[j];
				minx=j;
			}
		}
		check[minx]=true;
		//更新dist和values和pre cnt
		for(int j=0; j<n; j++) {
			if(edges[minx][j]>0) {//如果可达
				if(minv+edges[minx][j]<dist[j]) {
					dist[j]=minv+edges[minx][j];
					pre[j]=minx;
					values[j]=values[minx]+num[j];
					cnt[j]=cnt[minx];//最短路数量
				} else if(minv+edges[minx][j]==dist[j]) {
					cnt[j]+=cnt[minx];
					//如果救援队的数量更大
					if(values[j]<values[minx]+num[j]) {
						values[j]=values[minx]+num[j];
						pre[j]=minx;
					}
				}
			}
		}
	}
	cout<<cnt[d]<<" " <<values[d]<<endl;
	vector<int> vec;
	int x = d;
	vec.push_back(x);
	while(pre[x]!=-1){
		vec.push_back(pre[x]);
		x=pre[x];
	}
	reverse(vec.begin(),vec.end());
    for(int i=0;i<vec.size();i++){
    	cout<<vec[i];
    	if(i<vec.size()-1) cout<<" ";
	}
	return 0;
}