PTA 天梯赛习题集 L2-001 城市间紧急救援

城市间紧急救援

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式:
输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。

第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式:
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例:

2 60
0 1 3

大致思路：Dijsktra算法找到最短路径，在算法上稍加修改至在找最短路径时能选择尽可能携带更多救援队员。关于Dijsktra算法可以点击下面传送门了解详细。这篇博客就不细说了。
传送门：Dijsktra算法解析
AC代码（C++）

#include <iostream>
#include<algorithm>

#define MAXNUM 501 // 题目给出的最大不超过500
#define INF 100000000 // 假定无限大数
										   
using namespace std;					   
										   
int peoples[MAXNUM];					// 保存每个城市的救援人员人数，数组下标为城市编号
int peopleSum[MAXNUM] = {
     0 };			// 保存总救援人员数
int graph[MAXNUM][MAXNUM] = {
     0 };		// 保存邻接矩阵
int waySum[MAXNUM] = {
     0 };				// 保存路径
bool visit[MAXNUM] = {
     false };			// 标记已访问顶点
int prevNode[MAXNUM];					// 记录当前顶点的前驱顶点
int dist[MAXNUM];						// 保存最短路径
int inAllNum;							// 所有城市数，也就是输入的城市数

void print(int end, int start)			// 递归从后往前打印，从终点开始一直寻找前驱节点
{
    
	if (start == end)
	{
    
		cout << end;
		return;
	}
	print(prevNode[end], start);
	cout << " " << end;
}

void Dijkstra(int start)
{
    
	fill(dist, dist + inAllNum, INF);	// 假设刚开始所有地方都互相距离无穷远
	peopleSum[start] = peoples[start];	// 起点的救援队员人数直接加进总数
	waySum[start] = 1;					// 起点开始至少有一个路
	dist[start] = 0;					// 我们可以认为从起点到起点的距离为0
	int minNum = INF;					// 记录当前两个城市的最小距离，初始化为无限大
	int nodeNum = -1;					// 记录城市顶点编号，初始化为-1

	// 循环标记完所有城市即可
	for (int i = 0; i < inAllNum; i++)
	{
    
		// 记录城市与城市间的最小距离和城市顶点的两个变量每次循环都需要初始化一次
		minNum = INF;					// 存储从起点到其他未被访问节点中的最短距离
		nodeNum = -1;					// 存储最短距离节点的编号
		// 遍历n个顶点，寻找当前未被访问的顶点中的距离起始顶点最短距离的节点编号
		for (int j = 0; j < inAllNum; j++)
			// visit[j] 是false那么就是未被访问，表达式为真
			// 最短距离小于当前minNum的存储的数据，表达式为真
			// 满足以上条件即可进入判断
			if (!visit[j] && minNum > dist[j])
			{
    
				minNum = dist[j];
				nodeNum = j;
			}

		if (-1 == nodeNum)		// 没有找到符合条件的情况直接跳出循环
			break;
		visit[nodeNum] = true;	// 标记当前选择的顶点为已经访问

		// 以nodeNum为中间节点进行遍历其他顶点并计算距离
		for (int j = 0; j < inAllNum; j++)
		{
    
			// 如果当前遍历的节点j未曾作为过中间节点
		    // 并且从起始节点到j的距离dist[j]大于从起始节点到nodeNum与从nodeNum到j的距离之和
			if (!visit[j] && dist[j] > dist[nodeNum] + graph[nodeNum][j])
			{
    
				// 更新起始节点到j的距离dist[j]，更新为起始到nodeNum与nodeNum到j的距离之和
				dist[j] = dist[nodeNum] + graph[nodeNum][j];
				// 记录救援队人数
				peopleSum[j] = peopleSum[nodeNum] + peoples[j];
				// 记录当前顶点的前驱节点
				prevNode[j] = nodeNum;
				//记录路径数量
				waySum[j] = waySum[nodeNum];
			}
			// 如果当前遍历的节点j未曾作为过中间节点
			// 并且从起始节点到j的距离dist[j]等于从起始节点到nodeNum与从nodeNum到j的距离之和
			else if (!visit[j] && dist[j] == dist[nodeNum] + graph[nodeNum][j])
			{
    
				// 这句话写了意义不大因为a = 1, a == b 然后 a = b,a 还是等于 1 赋值的意义不大
				// dist[j] = dist[nodeNum] + graph[nodeNum][j];
				// 如果路过nodeNum顶点救援队员更多的话进行更新救援队人员数再修改前驱顶点
				if (peopleSum[j] < peopleSum[nodeNum] + peoples[j])
				{
    
					// 更新救援队人员数，尽可能要更多的救援队人员
					peopleSum[j] = peopleSum[nodeNum] + peoples[j];
					// 更换了行驶路线那么就得更新相应的前驱节点
					prevNode[j] = nodeNum;
				}
				// 因为路程出现相同距离的两个所有这两天路都可以选择所有得加上nodeNum顶点的路的数量
				// 不能直接waySum[j]++, 因为经过nodeNum顶点的方案中不只有一个路
				waySum[j] += waySum[nodeNum];
				
			}
		}
	}
}

int main()
{
    
	//N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；
	//M是快速道路的条数；
	//S是出发地的城市编号；
	//D是目的地的城市编号。
	int N, M, S, D;
	cin >> N >> M >> S >> D;
	//inAllNum也算城市的个数，全局变量方便其他函数访问
	inAllNum = N;
	//依次输入各个城市的救援队数量
	for (int i = 0; i < N; i++)
		cin >> peoples[i];
	//初始化邻接矩阵
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (i != j)
				graph[i][j] = INF;

	//给邻接矩阵赋值
	int tempa, tempb, tempc;
	for (int i = 0; i < M; i++)
	{
    
		cin >> tempa >> tempb >> tempc;
		graph[tempa][tempb] = tempc;
		graph[tempb][tempa] = tempc;
	}
	Dijkstra(S);
	cout << waySum[D] << " " << peopleSum[D] << endl;
	print(D, S);

	return 0;
}

下面分享几个测试样例，有测试点不能通过的朋友可以试试看。

样例（1）

6 6 0 3
30 10 20 50 20 20
0 1 1
2 3 3
0 4 1
1 2 2
5 3 3
4 5 2

样例（2）

6 7 0 3
30 100 20 50 20 20
1 3 5
2 3 3
1 2 2
5 3 3
0 4 1
4 5 2
0 1 1

样例（3）

5 5 0 3
30 100 20 50 120
0 4 1
0 1 1
1 2 1
4 3 5
2 3 3

样例（4）

7 8 0 6
10 20 30 50 30 30 20
0 1 1
0 2 1
1 3 2
5 6 4
3 4 3
3 5 3
4 6 4
2 3 2