L2-001 紧急救援 (25 分)

题目

题目链接

题解

最短路（扩展）

算是朴素Dijkstra模板吧。

Dijkstra算法

额外加上记录路径、记录到达此处的最短距离、记录以最短距离到达此处的最多人数。

更新方式：

假设未确定距离的点集中的点t距离已确定距离的点集最近，以t对其他未确定距离的点j进行松弛。即： 如果从s到j经过t的距离比不经过t短，则说明经过t更好，那么更新j的前一个节点为t，更新到达j的最大人数为到达t的最大人数+节点j的人数，更新到达j且距离最小的路径个数为到达t的路径个数；

如果从s到j经过t的距离与不经过t一样长，那么让到达j且距离最小的路径个数加上到达t的路径个数，即到达j且距离最小的路径个数应该包括距离最小的前提下，经过t和不经过t的路径个数和，所以是加上；再判断，如果经过t后j的人数会变多，那么更新j的前一个节点为t，更新到达j的最大人数为到达t的最大人数+节点j的人数。

如果从s到j经过t的距离比不经过t长，说明这条路径连最短路都不是，条件都满足不了，就不用处理了。

代码

#include
using namespace std;
const int N = 510;

int n, m, s, d, a[N], cnt[N], e[N][N], dis[N], pre[N], st[N], sum[N];


void path (int x) {
	if(pre[x] != -1) {
		path(pre[x]);
		cout  m >> s >> d;
	for (int i = 0;i > a[i];
	while (m --) {
		int a, b, c;
		cin >> a >> b >> c;
		e[a][b] = e[b][a] = c;
	}

	// 初始化
	dis[s] = 0;
	sum[s] = a[s];
	cnt[s] = 1;

	for (int i = 0;i