[数据结构与算法]L2-001 紧急救援 (25 分)

题意：

要求你求出最短路径的数量和最多的救援队的数量，并求S到D的的路径（该路径就是路径最短且召集救援队数量最多的路径）种经过的城市？

分析：

显而易见，这题要用dijkstra算法，不会该算法的可以去学一下，这里的难点在于如何求最短路径的数量和经过的城市，我们可以用三个数组存最短路径的数量，召集救援队的数量，这个点的前驱，然后在更新其它点的时候更新这些数组吗，详情请看代码。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++) 
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;

const int N = 510;

int n, m, s, d;
int g[N][N];
bool st[N];
int cnt[N], number[N]; // 分别用来存救援队的数量和最短路径的数量
int path[N]; // 记录一个点的前驱
int dist[N], w[N];

void dijkstra()
{
	memset(dist, 0x3f, sizeof dist);
	dist[s] = 0;
	cnt[s] = w[s]; //起始点的救援队数量
	number[s] = 1; //一开始最短路径为1
	
//	cout << dist[s] << ' ' << cnt[s] << ' ' << number[s] << endl;
	rep(i, 1, n)
	{
		int t = -1;
		rep(j, 0, n - 1)
			if(!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;
		st[t] = true;
		
		rep(j, 0, n - 1)
		{
			if(dist[j] > dist[t] + g[t][j])
			{
				dist[j] = dist[t] + g[t][j]; //更新最短路径
				cnt[j] = cnt[t] + w[j]; //更新救援队的数量
				path[j] = t; //记录前驱
				number[j] = number[t]; //更新最短路径的数量，因为这里只能从 t->j，即最短路径数量并不会改变
			}
			
			else if(dist[j] == dist[t] + g[t][j])
			{
				if(cnt[j] < cnt[t] + w[j]) // 考虑在路径相等的情况下，救援队的数量
				{
					cnt[j] = cnt[t] + w[j];
					path[j] = t;
				}
				
				number[j] += number[t]; //因为是t->j，加上t的最短路径的数量就是j的最短路径的数量
			}
		}
	}
}

int main()
{
	cin >> n >> m >> s >> d;
	rep(i, 0, n - 1) cin >> w[i];
	
	rep(i, 0, n - 1) path[i] = i;
	memset(g, 0x3f, sizeof g);
	
	rep(i, 1, m)
	{
		int x, y, z;
		cin >> x >> y >> z;
		g[x][y] = z;
		g[y][x] = z;
	}
	
	dijkstra();
	
	cout << number[d] << ' ' << cnt[d] << "\n";
	
	vector<int> ans;
	int p = d;
	while(1) //倒推路径
	{
		if(p == path[p])
		{
			ans.push_back(p);
			break;
		}
		
		ans.push_back(p);
		p = path[p];
	}
	
	pre(i, 0, ans.size() - 1) //逆序输出
	{
		if(i != 0) cout << ans[i] << ' ';
		else cout << ans[i] << "\n";
	}
	
	return 0;
}