PAT 甲级 1003 Emergency (25 分)题解

admin管理员组

文章数量:1577534

一、原题及翻译
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

作为一个城市救援队的领导者，你有一张你的国家的地图。这个地图上画着几个城市和他们之间的道路，救援队的数量和道路的长度也画在了地图上。你的工作是当有某个城市打来紧急呼叫时，带领着你的团队尽快前往那个城市，并且在沿途尽可能多地带上其他城市的救援队。

Input Specification:
输入格式：

每个输入文件包含一个案例。对于每个案例，第一行包含四个正整数-N（小于等于500）城市的数量（标号从0到N-1）；M-道路的数量；C1和C2-你现在所在的城市和你要去的目标城市。下一行包括N个整数，其中第i个数字代表第i个城市里救援队的数目。接下来是M行，每一行包括c1，c2，和L，代表着从城市c1到城市c2之间的道路长度。题目保证至少存在一条从C1到C2的道路。
Output Specification:
输出格式：

对于每一个测试案例，在一行当中打印两个数字，第一个是C1到C2最短路径的条数，第二个数字你可以收集到的救援队最大数目。两个数字时间由空格分开，末尾不能有额外的空格。
Sample Input:
输入样例：

5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

Sample Output:
输出样例：

2 4

二、个人解析
这道题我淦了好久，最后还是看到柳神的题解才做出来（感谢柳神）
思路就是用一边Dijkstra算法，每个城市救援队的个数相当于权值。
比较重要的变量：
dis[i] ~ 从C1到i城市最短距离
num[i] ~ 从C1到i城市最短距离的条数
w[i] ~ 从C1到城市i能收集到的救援队最大量
然后就是Dijkstra算法，在更新dis[i]时，同时更新num和w，当发现dis[i]和dis[k]+e[k][i]相等时，就遇到了距离相同的最短路径，然后最短路径数目就要增加为num[i] = num[i] + num[k]，权重就要进行比较了，比较完之后更新w。
然后对于Dijkstra算法，我是从这篇文章学明白的（感谢这篇文章的作者）
https://blog.csdn/qq_35644234/article/details/60870719
三、代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
#include<string>
#include<cmath>
#include<utility>
#define inf 9999999
using namespace std;
int n, m, c1, c2;
int findmin(int dis[], int visit[])
{
	int minn = inf;
	int k = -1;
	for (int i = 0; i < n; i++)
	{
		if (minn > dis[i] && visit[i] == 0)
		{
			minn = dis[i];
			k = i;
		}
	}
	return k;
}
int main()
{
	cin >> n >> m >> c1 >> c2;
	int city[501] = { 0 };
	int e[501][501] = { 0 };
	int dis[501] = { 0 };
	int visit[501] = { 0 };
	int w[501] = { 0 };
	for (int i = 0; i < n; i++)
	{
		dis[i] = inf;
		cin >> city[i];
	}
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		e[a][b] = e[b][a] = c;
	}
	dis[c1] = 0;
	w[c1] = city[c1];
	int num[501] = { 0 };
	num[c1] = 1;
	for (int i = 0; i < n; i++)
	{
		int k = findmin(dis, visit);
		if (k == -1)
			break;
		visit[k] = 1;
		for (int l = 0; l < n; l++)
		{
			if (e[k][l] != 0 && visit[l] != 1)
			{
				if (dis[k] + e[k][l] < dis[l])
				{
					dis[l] = dis[k] + e[k][l];
					num[l] = num[k];
					w[l] = w[k] + city[l];
				}
				else if (dis[k] + e[k][l] == dis[l])
				{
					num[l] = num[l] + num[k];
					if (w[k] + city[l] > w[l])
						w[l] = w[k] + city[l];
				}
			}
		}
	}
	cout << num[c2] << " " << w[c2] << endl;
	return 0;
}

本文标签： 题解PATEmergency