PTA甲级刷题1003 Emergency（详细注释版+思路总结）

admin管理员组

文章数量:1577496

目录看这里大哥们！

• PAT甲级刷题笔记（C++）
• • 1003 Emergency（最短路径搜索）
  • • （1）题目
    • （2）代码和注释
    • （3）归纳与反思
    • （4）运行结果
    • （5）其他大哥的链接

PAT甲级刷题笔记（C++）

Hello!朋友们俺也来写博客啦~
最近在开始刷PAT的甲级真题，欢迎大噶一起来讨论还有互相监督刷题吖~后面也会陆续更新更多题目的刷题思路和完整代码！让我们冲冲冲吖！

• 写在前面：希望大家都能走花路~

1003 Emergency（最短路径搜索）

（1）题目

• 英语原题
  

• 中文意译
  你是城市救援队的领导者，你手中有一张求援地图（包括：各个城市的救援队伍数，各个城市之间的路线和距离等）。当有险情时，你需要尽快地做出指挥，使救援队伍尽可能快地到达受灾区，当同样快的前提下，调动救援队伍数更多的那个路线方案。

  • 示例输入

  ---

  第1行：5 6 0 2
  ①城市数N<=500，城市序号(0~N-1)
  ②路的数量M
  ③起点城市序号C1
  ④终点城市序号C2【需救援的城市】
  第2行：1 2 1 5 3
  按序号从小到大排列的各个城市分别拥有的救援队伍数量
  第3行~第X行：0 1 1 ……
  X的计算：X=M-3+1
  每一行均表示：n1 n2 length
  即地图上某两个城市之间（n1, n2）的距离length

  • 示例输出

  ---

  输出：2 4
  2：最短路径的条数
  4：各种最短路径方案中加起来得到的总救援队伍个数

（2）代码和注释

• 实现方式①

#include<iostream>
#define Maxn 10000
using namespace std;
int map[500][500]={0};

int main(){
	int N,M,C1,C2;
	cin>>N>>M>>C1>>C2;
	int rescue[N];
	int Point[N]={0};//点权 
	int value[N];//C1城市到其他城市的距离 
	bool S[N]={false};//S集合用来判断已经走过的点 
	int	line[N]={0};//记录C1到其他城市最短距离的条数 
	
//---------------读入数据以及初始化---------------------
    for(int i=0;i<N;++i){
		cin>>rescue[i];
	}
	for(int i=0;i<N;++i){
		for(int j=0;j<N;++j){//初始化邻接矩阵 
			if(i==j)
			map[i][j]=0;
			else
			map[i][j]=Maxn;
		}
		if(i==C1){
			//起点到自己的路线的条数
			line[i]=1; 
			//起点的边权(自己到自己的距离)为0 
			value[i]=0;
			//起点的点权为该城市救援队的数量 
			Point[i]=rescue[i];
		}
		else{
			//起点到其他点的边权都设置为最大值 
			value[i]=Maxn;
		} 
	}
	for(int i=0;i<M;++i){
		int c1,c2,l;
		cin>>c1>>c2>>l;
		map[c1][c2]=l;
		map[c2][c1]=l;
	}
//---------------读入数据以及初始化---------------------
    
	while(1){
		int t=Maxn,temp=-1;//t为临时边权值，temp为当前的临时点
    // ---------------找到从起点出发到达其他城市的当前最小距离（边权）----------------
		for(int i=0;i<N;++i){
			if(S[i]==true)
			continue;
			if(value[i]<t){
				t=value[i]; 
				temp=i;//找到边权最小的点
			}
		}
    // ---------------从边权最小的temp城市再次出发搜索，若temp城市刚好是C2欲救援的城市，则break输出----------------
    // -------------【temp==C2 此处不是贪心算法，因为后面的更新全都是加法，只会让距离越来越大】--------------------
    // -------------【t==Maxn 当所有路径都遍历完时，即其他城市都当过中转点时，目的地C2即value[C2]已保持最新且最短的状态，此时t==Maxn，break输出】--------------------
		if(t==Maxn||temp==C2)break;

    // ---------------记录下已走过的点，不要出现折返的情况----------------
		S[temp]=true;
        
    // ---------------以temp城市作为新的起点（实际为中转点）进行新一轮的列搜索（除去已经过的城市），更新到达其他城市（包括目的地）的边权、点权----------------
		for(int i=0;i<N;++i){
			if(S[i]==true)//排除自己这个点
			continue;
			if(value[i]>value[temp]+map[temp][i]){//如果当前的边权小于之前的边权，更新边权，点权和路线条数
				value[i]=value[temp]+map[temp][i];//边权等于上一个点的边权加上当前边的距离（即point到i的距离）
				Point[i]=Point[temp]+rescue[i];//点权等于上一个点的点权加上当前点的点权（即当前点的救援队数量）
				line[i]=line[temp];//更新最短路径数 
			}
            else if(value[i]==value[temp]+map[temp][i]){
				if(Point[i]<Point[temp]+rescue[i]){
					Point[i]=Point[temp]+rescue[i];
				}
                
    // ---------------同样出现最短距离时才叠加最短路径数，若发现此时的路径不是最短路径，则在上一个if中则会重新将line[i]置1----------------
				line[i]=line[i]+line[temp];
			}
		}
	}
	cout<<line[C2]<<" "<<Point[C2];
	return 0;
} 

• 实现方式②

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, c1, c2;//城市个数、路的数量、出发城市、救援城市
int e[500][500];//edge

//dis表示从出发点到i结点最短路径的路径长度
//num表示从出发点到i结点最短路径的条数
//w表示从出发点到i点救援队的数目之和
int weight[500], dis[500], num[500], w[500];
bool visit[500]; 
const int inf = 99999999;

int main()
{
    cin>>n>>m>>c1>>c2;
    for(int i=0;i<n;i++)
        cin>>weight[i];
    //initial
    fill(e[0],e[0]+500*500,inf);//设置为无穷
    fill(dis,dis+500,inf);
    
    //读入边的权重
 int a,b,c;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        e[a][b]=e[b][a]=c;
    }
    
    //初始化计数
    dis[c1]=0;
    w[c1]=weight[c1];//目前队伍个数
    num[c1]=1;//路径数量
    
    //Dijkstra
    //for(int i=0;i<n;i++)
    //{
        
    //}

    
    //Dijkstra算法核心
 for (int i = 0; i < n; i++) 
 {
  int u = -1, minn = inf;
  //找到当前距离源点最近的点
  for (int j = 0; j < n; j++) 
  {
   if (visit[j] == false && dis[j] < minn) 
   {
    u = j;
    minn = dis[j];
   }
  }
  if (u == -1) break; //如果以上的点都被遍历完就停止
  visit[u] = true;
  //寻找经过该中转点可以直接到达的点，其实就是dijkstra的思想
  for (int v = 0; v < n; v++) //n是城市个数
  {
   if (visit[v] == false && e[u][v] != inf) 
   {
    if (dis[u] + e[u][v] < dis[v]) //如果此时是最短路径 
    {
     dis[v] = dis[u] + e[u][v]; //更新最短路径长度
     num[v] = num[u];           
     w[v] = w[u] + weight[v];   //更新最短路路径的最大队伍数量
    }
    else if (dis[u] + e[u][v] == dis[v]) 
    {
     num[v] = num[v] + num[u];
     if (w[u] + weight[v] > w[v])
      w[v] = w[u] + weight[v];
    }
   }
  }
 }
 printf("%d %d", num[c2], w[c2]);
 return 0;
    
}

（3）归纳与反思

• 该题的重要思想

---

（1）读取确定起点之后不要总想着要把起点到终点的路径遍历完，要同时允许到达其他城市的最短距离也在更新，路径也在遍历。
（2）而其他城市最短路径的遍历实际也是为其他城市作为中转点的路径遍历 的计算过程中，不得已额外算的。
（3）有条件式搜索：
①每次都在最短的边权下进行搜索；②不要再次经过之前的城市。

• 一开始没做出来的原因

---

失败的原因1：
暴力破解，自己想最短路径的思路，但是程序没跟上【没有正确解耦】

失败的原因2：
我想把所有的路径搜索完再来比较谁最短，则会出现两个难点：
1）得到所有的路径计算量大，也比较复杂
2）路径的存储也困难

失败的原因3：
变量的选取还是差点意思，既然路径搜索是层层搜索，那就应该创建出各层中存在的节点的位置，然后不断更新到达各节点的最短路径。

失败的原因4：
同样是从起点开始考虑，但是我没有预留出起点相关的变量。
1）起点到达其他城市的总救援队数量
2）起点到其他城市最短距离的道路条数
3）起点到其他城市的距离【不断更新，使其保证当前最小】

（4）运行结果

（5）其他大哥的链接

PAT1003 Emergency(c++实现)—甲级真题
Dijkstra算法图文详解

• 写在后面：特此鸣谢被我一喊就过来刷这个题，还全对的大哥yzh~

本文标签： 注释思路详细PTAEmergency