[PAT甲级] 1003. Emergency

admin管理员组

文章数量:1577818

问题描述

 大致意思是：

某个地方有需要急救的病人，而你在c1处，病人在c2处，(c1、c2都是某个城市的编号)，每座城市都有自己的急救队伍，输入会给出每座城市的急救队伍的数量以及相互可达的城市之间的距离，让你找出c1到c2的最短路径的个数，以及在这些最短的路径里面能召集到急救人员的最大数量。

输入

第一行：N(城市的个数)   M(路径的个数)   c1(起点)   c2(目的地)

第二行：N个数，分别代表第i个城市所拥有的急救团队的数量

接下来的M行：每行给出三个数   分别是：城市1的序号   城市2的序号   二者之间的距离

要求输出

最短路径的个数   和    这些最短路径里面最多能召集多少急救队伍

思路

很明显题目要我们去考虑两点间的最短路径，让我想起了学数据结构的图那一章的一些知识(虽然已经忘得差不多了...) 

这里他不强调两城市之间是不是单向可达，所以我们按双向可达来处理，即用无向图来处理。

可以用一个二维数组，比如map[i][j] 的值就是i号城市和j号城市之间的距离，可以用0或者别的特殊值来表示不可达。

然后至于最短路径的求法，就应该用到深度优先(dfs)或者广度优先(bfs)来递归实现了。

       在每一次的递归中，我们首先要知道自己当前在哪个城市，然后要知道我们从起点开始走到当前点用了多少距离，聚集了多少队伍。也就是dfs(int cur, int  distance,  int  team_num)

       因为是无向图，所以可能在往下递归时会重新访问到上一次访问过的点，造成死递归。

       那么我们可以把这个当成一个退出条件，我们每次递归都会传入当前累计走过的距离，而每次递归距离都会增大，可以用一个数组记录从起点到达每一个点所用的最短距离，那么如果我这次到达当前点用的距离比数组里记录的最短距离要大，那这条路肯定不会是最短路(即有可能是重复走了某几个点导致的)，此时直接退出(return)。

然后，到达目的地时的处理：

题目要求我们记录所有最短路径里能够召集到的最大救援队伍数量，以及距离最短的路径到底有多少条，因此我们在到达目的地是要对这两个值进行更新。

1)、若当前累计距离比最短距离数组里记录的要小，那么说明当前的这条路径才是唯一最短的一条路径，那么最短路径数应该置为1，并且最大救援数量直接等于这条路径召集的救援队数量。

2)、若当前累计距离和数组里记录的一样，那说明当前路径是一条并列最短的路径，则路径数加一，然后当前的救援队数要和最大救援队数作比较，若当前聚集的救援队更多，则更新。

大致思路就这些，接下来贴代码---------------------------------------------------------------------------------------

代码

#include<iostream>
using namespace std;

/*
    2022/11/27 
    无向图
	最短路径
	dfs 
*/ 

int N,M,max_team_num = 0;
int destination,paths=0;
// 地图数组 , 和每个城市拥有的急救队伍数组 
int map[500][500],emergency[500];

// 表示到任意一点的最短距离 
int shortest[500]; 


// 深度优先计算最短路径并更新最短路径数组。 
void dfs(int cur,int distance,int team_num){
	//若到达当前点的累计距离比上一次到达时记录的最短距离还要大，那么这条路就没
	//必要再走下去了，所以直接返回 
	if(distance>shortest[cur])
		return;
	
	if(cur == destination){
		//若当前位置就是目的地
		if(distance<shortest[cur]){
			//若这次到达目的地的累计距离比之前记录的要短，那就更新并结束函数 
			shortest[cur] = distance;
			paths = 1;
			max_team_num = team_num;
		}else{
			//距离和之前某个路径的一样，那就paths+1 即多了一条并列最短的路线 
			paths++;
			//若当前累计的队伍数比之前记录的最大值大，那么就更新
		    max_team_num = team_num>max_team_num?team_num:max_team_num;
		}
	}else{
		// 若当前累计的路径长度比上一次到达这个点的距离要短，那么就更新。 
		if(distance<shortest[cur]){
			shortest[cur] = distance;
		}
		//当前点还没到最终点
		for(int i=0;i<500;i++){
			//如果当前点与第i个点相邻，就进去递归 
			if(map[cur][i]!=-1){
			    dfs(i,distance+map[cur][i],team_num+emergency[i]);
		    }
	    }
    }
}

int main(){
	int c1,c2;
	int temp1,temp2,l;
	cin>>N>>M>>c1>>c2;
	
	destination = c2;
	
	// 距离(地图)二维数组初始化 
	for(int i=0;i<500;i++){
		// 先弄个比较大的数当最短距离 
		shortest[i] = 1000000000; 
		for(int j=0;j<500;j++){
			// 距离为-1 初始化为不可达 
			map[i][j] = -1;
		}
	}
	
	// 输入急救队伍数组 
	for(int i=0;i<N;i++){
		cin>>emergency[i];
	}
	
	for(int i=0;i<M;i++){
		cin>>temp1>>temp2>>l;
		// 记录两点之间的距离(无向图) 
		map[temp1][temp2] = map[temp2][temp1] = l;
	}
	
	// 开始深度优先计算最短路径 
	dfs(c1,0,emergency[c1]);
	cout<<paths<<" "<<max_team_num<<endl; 
	
	return 0;
} 

结果如下：

本文标签： PATEmergency