还是学习了一下别人,注解明天补齐,建议这题使用scanf输入,最后一个点比较吃时间

题目地址 L2-001 紧急救援 (25 分)

#include <bits/stdc++.h>
#define MAX 560
#define INF 23333
using namespace std;
int Map[MAX][MAX], wei[MAX], dist[MAX], vis[MAX], city[MAX], sum[MAX], side[MAX];
int n, m, s, d, start, done, len, mins, Index;

void init() {
	memset(Map,INF,sizeof(Map));
	memset(dist,INF,sizeof(dist));
}

void Dij() {
	//根据起点初始化  
	dist[s]=0;
	city[0] = s;
	side[s] = 1;
	sum[0] = wei[0];
	//Dijkstra
	for(int i = 0; i < n; i++) {
		mins = INF;
		Index = 233;
		//找最近的点 
		for(int j = 0; j < n; j++) {
			if(!vis[j] && dist[j] < mins) {
				mins = dist[j];
				Index = j;
			}
		}
		//标记 
		vis[Index] = 1;
		for(int j = 0; j < n; j++) { 
			// 0-3  跟 0-1-3的长度是一样的  但是要求找更多的救援队 
			if(!vis[j] && Map[Index][j] + dist[Index] < dist[j]){
				// 救援队直接加上 
				sum[j] = sum[Index] + wei[j];
				// 更新dist  
				dist[j] = Map[Index][j] + dist[Index];
				// 记录从哪里来 
				city[j] = Index;
				 
				side[j] = side[Index];
			}else if(!vis[j] && Map[Index][j] + dist[Index] == dist[j]) {
				if(sum[Index] + wei[j] > sum[j]) {
					sum[j] = sum[Index] + wei[j];
					city[j] = Index;
				}
				side[j] += side[Index];
			}
		}
	}
}

void print(int start, int end) {
	if(end == start){
		cout<<start;
		return;
	}
	print(start,city[end]);
	cout<<" "<<end;
} 
int main() {
	init();
	cin>>n>>m>>s>>d;
	for(int i = 0; i < n; i++)
		cin>>wei[i];
	for(int i = 0; i < m; i++) {
		cin>>start>>done>>len;
		Map[done][start] = Map[start][done] = len;
	}
	for(int i = 0; i < n; i++)
		city[i] = i;
	Dij();
	cout<<side[d]<<" "<<sum[d]<<endl; 
	print(s,d);
	return 0;
}