天梯赛练习L2-001. 紧急救援

题目链接：https://www.patest.cn/contests/gplt/L2-001

代码：

// 这张图是一张 无向 有环 带权 图， 考察一下我们常用的找最短路径的方案，bfs
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 500 + 10;
const int maxm = 1000000 + 10;
const int inf = 1 << 30;
struct Edge
{
	int v;
	int w;
	int next;
}edge[2 * maxm];
int dist[maxn], head[maxn], people[maxn], pos, pre[maxn], pathNum[maxn], getPeople[maxn];
int n, m;
void addEdge(int u, int v, int w){
	edge[pos].v = v;
	edge[pos].w = w;
	edge[pos].next = head[u];
	head[u] = pos;
	pos++;
}
void init(){
	for(int i = 0; i < maxn; i++) head[i] = -1;
	for(int i = 0; i < maxn; i++) pre[i] = -1;
	for(int i = 0; i < maxn; i++) pathNum[i] = 0;
	for(int i = 0; i < maxn; i++) getPeople[i] = 0;
	pos = 0;
}
void Dijkstra(int s, int t){
	for(int i = 0; i < n; i++) dist[i] = inf; // 初始化s到其他点的举例
	// 初始化s
	dist[s] = 0;
	pathNum[s] = 1; 
	getPeople[s] = people[s];
	pre[s] = -1;

	int V[maxn]; // V为0的是Vb集合元素，V为1是Va集合元素
	memset(V, 0, sizeof(V));
	for(int i = 0; i < n; i++){ // 每次选取Vb中最近的点加入Va（n个点）
		int u = -1, minimum = inf;
		for(int j = 0; j < n; j++){ // 选取Vb中dist最近的点
			if(!V[j] && dist[j] < minimum){
				minimum = dist[j];
				u = j;
			}
		}
		V[u] = 1; // 加入Va
		//用u更新Vb中所有和u相邻的点的距离和其他信息
		for(int k = head[u]; k != -1; k = edge[k].next){
			int v = edge[k].v;
			if(!V[v]){
				if(dist[v] > edge[k].w + dist[u]){
					dist[v] = edge[k].w + dist[u];
					pre[v] = u;
					getPeople[v] = getPeople[u] + people[v];
					pathNum[v] = pathNum[u];
				}
				else if(dist[v] == edge[k].w + dist[u]){
					pathNum[v] += pathNum[u];
					if(getPeople[v] < getPeople[u] + people[v]){
						pre[v] = u;
						getPeople[v] = getPeople[u] + people[v];
					}
				}
			}
		}
	}
}

void printPath(int s, int t){
	int road[maxn];
	int p = t;
	int cnt = 0;
	while(p != -1){
		road[cnt] = p;
		p = pre[p];
		if(p< -1 ||p > n){
			cout << "shit"<< endl;
			break;
		}
		cnt++;
	}
	for(int i = cnt - 1; i >= 0; i--){
		printf("%d", road[i]);
		if(i != 0) printf(" ");
	}
	printf("\n");
}
int main(){
	//freopen("input.txt", "r", stdin);
	int s, t;
	scanf("%d%d%d%d", &n, &m, &s, &t);
	init();
	for(int i = 0; i < n; i++) scanf("%d", &people[i]);
	for(int i = 0; i < m; i++){
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		addEdge(u, v, w);
		addEdge(v, u, w);
	}
	Dijkstra(s, t);
	printf("%d %d\n", pathNum[t], getPeople[t]);
	printPath(s, t);
	return 0;
}