【PAT（甲级）】1003 Emergency

admin管理员组

文章数量:1577577

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

解题思路：

题目要求最短路径的条数和救援队数量（可以看成点的权重），很明显就是一个最短路径算法的检验。所以很自然地想到用dijkstra算法（Floyd应该也可以，但我不熟悉这个算法，你们自己可以试着写一下）。然后在此基础上加上一个tol[]数组来存储每个点上最短路径的条数即可。

对于dijkstra算法并不熟悉的同学也可以先尝试着读一下我的代码，代码里的注释还是比较详细的，也许也能帮到你更好地理解算法。

易错点：

在使用迪杰斯特拉算法时，需要注意，应该默认最短路径数量为1（起点自己到自己）；

在循环时，循环的点数量为总的点个数数量；

代码：

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int N=0;//城市数量 
int M=0;//街道数量
int C1,C2;//所在和目的城市
int Saver[500];//下标代表城市，数组内存放对应城市的救援队数量 
int edage[500][500];//下标表示城市，数组存放两个城市之间的距离
int tol[500]={0};//最短路径的数量
int max_s[500]={0};//最大救援队的数量 

//dijkstra算法所需 
int dist[500];//记录当前所有点到起点的距离
int visit[500]={0};//标记当前点是否已经被访问过 
const int inf = 10000000;
 
 
void read_G(){//按照题目要求读取信息 
 	cin>>N>>M>>C1>>C2;
 	fill(edage[0],edage[0]+500*500,inf);
	for(int i=0;i<N;i++){
		cin>>Saver[i];
	}
	for(int i=0;i<M;i++){
		int a1,a2;
		cin>>a1>>a2;
		cin>>edage[a1][a2];
		edage[a2][a1]=edage[a1][a2]; 
	} 
 }
 
void Dijkstra(int C){
	fill(dist,dist+500,inf);
	dist[C]=0;
	max_s[C]=Saver[C];//一开始，默认自己城市的救援队数量为最大数量 
	tol[C]=1;//默认自己到自己为1)
 	for(int i=0;i<N;i++){
 		int index=-1;//表示当前距离原点最近点的下标 
		for(int j=0;j<N;j++){
			if(visit[j]==0&&(index==-1||dist[j]<dist[index])){
				index = j;
			}
		} 
		
		if (index==-1) return;
		visit[index]=1;//将此点标记为已经访问过
		for(int j=0;j<N;j++){//重新循环所有城市 
			if(visit[j]==0&&edage[index][j]!=inf){//对没有访问过，且城市与城市之间相通的 ，最短路径还有救援队人数进行更新 
				if(dist[index]+edage[index][j]<dist[j]){
					dist[j]=dist[index]+edage[index][j];
					max_s[j]=max_s[index]+Saver[j];
					tol[j]=tol[index];
				}
				else if(dist[index]+edage[index][j]==dist[j]){//相等说明最短路径需要加上一条，且需要判断救援队人数大小 
					if(max_s[j]<max_s[index]+Saver[j]){
						max_s[j]=max_s[index]+Saver[j];
					}
					tol[j]+=tol[index];
				}
			}
		} 
	} 
 } 
 
int main(){
	read_G();
	Dijkstra(C1);
	cout<<tol[C2]<<" "<<max_s[C2]<<endl; 
	return 0;
}

本文标签： PATEmergency