1003 Emergency 题目解析

admin管理员组

文章数量:1577500

文章目录

• 题目描述
• 题意理解
• 解题思路
• 核心算法
• 完整代码

题目描述

1003 Emergency
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:
Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.

Output Specification:
For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

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

题意理解

• (人工渣翻)作为城市的紧急救援队队长，你被给予了一份特殊的国家地图。地图展示了几个由道路连通起来的散落城市，并且标出了每个城市拥有的救援队数量、道路长度。当急救电话响起时，你的工作是带领你的队员以最快的速度赶到救援地点，同时你要尽可能多的叫上途径城市的救援队队员。
• 输入第一行为四个正整数：N(城市数量)，M(道路数量)，C1(出发地)，C2(目的地)。第二行输入N个整数，表示每个城市的救援人员数量(城市编号从0开始)
• 你的输出包含两个数：最短路径的数量和能搜集到的人手的最大数量。数字之间以空格隔开，并且行末不能有多余空格或空行

解题思路

• 这道题是很明显的Dijkstra算法的变形，实际不难，但首先要求学生对原始Dijkstra算法已经很熟练，如果还是不会写或者不理解原始的Dijkstra算法，还是先去巩固基础吧。
• 原点已经给出，则只要进行一次Dijkstra就能得出答案，但是这道题要求的是计算最短路径的数量而不是最短路径的长度，同时在保证路径最短的同时要记录能搜集到的最多的人手数量，因此，除了原始的Dijkstra算法之外，我们还应该设置两个数组：一个用来记录从原点到该节点所能选择的最短路数量(num)，另一个用来记录从原点到该节点所能搜集到的帮手的最大数量(teams)，最后直接输出num[C2]，teams[C2]就可以了
• 图存储城市直接路径长度，如果不连通，就置为INFINITY(无限大)，同时设置一个teamsInCity数组，存储每个城市所含救援队队员数量
• 核心代码整体思路是很简单的，只要在更新最短路径的同时更新teams数组，然后再加一个if：如果发现当前路径长度与上一个最短路径长度相同，则num++，并且比较这条路所能搜集到的帮手数是否大于上一次记录的最大帮手数，如果更大就更新teams就行了

核心算法

• 根据上述思路，我们可以写出以下伪代码(num,teams,vis已全初始化为0,dist已初始化全为INF)：

void Dijkstra()
{
	初始化原点S,即出发城市的dist[S],num[S],teams[S]
	while (1) {
		查找还未被访问过的城市中路径最短的城市;
		如果找不到就说明已经无未被访问过的连通城市，则返回;
		访问当前城市;
		遍历所有城市 {
			if (如果未访问过 && 路径更短) {
				更新路径长度;
				更新路径数量;
				更新人手数量;
			}
			else if (如果未访问过 && 路径与最短路径长度相同) {
				更新路径数量;
				if (如果能搜集到更多人手)
					更新人手数量;
			}
		}
	}
}

• 重点在于如何更新路径数量和更新人手数量，当第一次访问到该城市时，该城市的num一定为0，teams也为0。对于num，既然是第一次访问，那么到达该城市的路径数量一定等于到达该城市之前上一个城市(其前驱节点)的路径数量，如果后序又有其他最短路径能到达该城市，则它就会进入else-if，这时，该城市肯定就不是第一次途径了，它的num就不为0了，此时要做的就是将它原本的最短路径数加上当前前驱城市的路径数，即num[cur] += num[pre]；对于teams则比较简单，比较它的大前提是路径首先得最短，所以当找到新最短路径跟dist一样直接更新就行，当最短路径相同时，比较该条路上能搜集到的人手是不是更多，是的话直接更新
• 于是就能写出下面的代码：

void Dijkstra()
{
	dist[S] = 0;
	num[S] = 1;
	teams[S] = teamsInCity[S];
	while (1) {
		int u = -1, min = INF;
		for (int i = 0; i < N; i++)
			if (min > dist[i] && !vis[i]) {
				u = i;
				min = dist[i];
			}
		if (u == -1)return;
		vis[u] = true;
		for (int i = 0; i < N; i++)
			if (!vis[i] && dist[i] > dist[u] + map[u][i]) {
				dist[i] = dist[u] + map[u][i];
				num[i] = num[u];
				teams[i] = teamsInCity[i] + teams[u];
			}
			else if (!vis[i] && dist[i] == dist[u] + map[u][i]) {
				num[i] += num[u];
				if (teams[i] < teamsInCity[i] + teams[u])
					teams[i] = teamsInCity[i] + teams[u];
			}
	}
}

• 核心代码写出来了其他就该怎么来怎么来了

完整代码

#include <iostream>
#define MAXN 500
#define INF 0xffffff
using namespace std;

int N, M, S, D, teamsInCity[MAXN], map[MAXN][MAXN], num[MAXN] = { 0 }, dist[MAXN], teams[MAXN];
bool vis[MAXN] = { false };

void Dijkstra()
{
	dist[S] = 0;
	num[S] = 1;
	teams[S] = teamsInCity[S];
	while (1) {
		int u = -1, min = INF;
		for (int i = 0; i < N; i++)
			if (min > dist[i] && !vis[i]) {
				u = i;
				min = dist[i];
			}
		if (u == -1)return;
		vis[u] = true;
		for (int i = 0; i < N; i++)
			if (!vis[i] && dist[i] > dist[u] + map[u][i]) {
				dist[i] = dist[u] + map[u][i];
				num[i] = num[u];
				teams[i] = teamsInCity[i] + teams[u];
			}
			else if (!vis[i] && dist[i] == dist[u] + map[u][i]) {
				num[i] += num[u];
				if (teams[i] < teamsInCity[i] + teams[u])
					teams[i] = teamsInCity[i] + teams[u];
			}
	}
}

void Emergency()
{
	for (int i = 0; i < N; i++)
		dist[i] = INF;
	Dijkstra();
	cout << num[D] << ' ' << teams[D];
}

int main()
{
	cin >> N >> M >> S >> D;
	for (int i = 0; i < N; i++)
		cin >> teamsInCity[i];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			map[i][j] = INF;
	for (int i = 0; i < M; i++) {
		int c1, c2, len;
		cin >> c1 >> c2 >> len;
		map[c2][c1] = map[c1][c2] = len;
	}
	Emergency();
	return 0;
}

本文标签： 题目Emergency