L2-001 紧急救援 （25 分) 最短路

Dijkstra维护两个值。递归找起点。

Code：

#include <bits/stdc++.h>
const int inf = 1e9 + 7;
const int maxn = 505;
int a, b, c, n, m, ss, ee;
int dis[maxn], s[maxn][maxn], cnt[maxn], people[maxn], num[maxn], pre[maxn];
bool book[maxn];
using namespace std;
void print(int k)
{
	if (k == ss)
	{
		printf("%d", ss);
		return;
	}
	print(pre[k]);
	printf(" %d", k);
}
int main()
{
	scanf("%d%d%d%d", &n, &m, &ss, &ee);
	for (int i = 0; i < n; i++)
		scanf("%d", &people[i]);
	fill(dis, dis + maxn, inf);
	fill(s[0], s[0] + maxn * maxn, inf);
	fill(book, book + maxn, false);
	while (m--)
	{
		scanf("%d%d%d", &a, &b, &c);
		s[a][b] = c;
		s[b][a] = c;
	}
	dis[ss] = 0;
	cnt[ss] = 1;
	num[ss] = people[ss];
	for (int i = 0; i < n; i++)
	{
		int f = -1, minn = inf;
		for (int j = 0; j < n; j++)
		{
			if (book[j] == false && dis[j] < minn)
			{
				f = j;
				minn = dis[j];
			}
		}
		book[f] = true;
		if (f == -1)
			break;
		for (int j = 0; j < n; j++)
		{
			if (book[j] == false && dis[j] > dis[f] + s[f][j])
			{
				dis[j] = dis[f] + s[f][j];
				cnt[j] = cnt[f];
				num[j] = num[f] + people[j];
				pre[j] = f;
			}
			else if (book[j] == false && dis[j] == dis[f] + s[f][j])
			{
				cnt[j] += cnt[f];
				if (num[j] < num[f] + people[j])
				{
					num[j] = num[f] + people[j];
					pre[j] = f;
				}
			}
		}
	}
	printf("%d %d\n", cnt[ee], num[ee]);
	print(ee);
}