团体程序设计天梯赛-练习集 L2-001 紧急救援 (25分) 最短路+回溯思想

叁歲伎倆 2023-10-11 14:52 14阅读 0赞

### L2-001 紧急救援 (25分) ###

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

**输入格式:**  
输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。

第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

**输出格式:**  
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

**输入样例:**

4 5 0 3
    20 30 40 10
    0 1 1
    1 3 2
    0 3 3
    0 2 2
    2 3 2

**输出样例:**

2 60
    0 1 3

> 本题思路：实际上本题是基于最短路径Dijkstra算法的一道衍生题目，其另外的需要注意的是当路径长短相同的时候需要比较得出最多的求援人员的数目，另外就是得出最短路的过程中需要记录城市的编号，因为最后需要输出。这里涉及的是一点回溯的思想。下面这个链接是我对最短路的一点总结，程序可直接用。  
> [最短路的总结参考本人的另一篇文章 https://blog.csdn.net/weixin\_43819566/article/details/109068258][https_blog.csdn.net_weixin_43819566_article_details_109068258]

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<cstdio>
    #include<string>
    #define Inf 0x3f3f3f
    const int N = 505;
    using namespace std;
    int n, m, s, d;//城市编号，快速通道条数，出发城市编号，目的城市编号
    int dis[N];//求出发点到各点的最小值
    int vis[N];//标志是否被访问过的状态
    int num[N];//每个城市的救援队人数
    int P[N];//保存前驱
    int number[N];//保存到达第i个城市可容纳的最多人数
    int Graph[N][N];//邻接矩阵
    int cnt[N];//保存到第i个城市的最短路径条数
    
    void init(){
        
    	memset(Graph, Inf, sizeof(Graph));
    	for(int i = 0; i < n; i ++){
        
    		Graph[i][i] = 0;
    	}
    }
    void getGraph(){
        
    	int ci1, ci2, len;
    	for(int i = 0; i < m; i ++){
        
    		cin >> ci1 >> ci2 >> len;
    		Graph[ci1][ci2] = Graph[ci2][ci1] = len;
    	}
    }
    void Dijkstra(int s, int d){
        
    	for(int i = 0; i < n; i ++){
        
    		P[i] = s;//初始化每个城市前驱为s
    		number[i] = 0;
    		vis[i] = 0;
    	}
    	number[s] = num[s];
        cnt[s] = 1;//到达第s个城市的最短路径只有一条
    
    	for(int i = 0; i < n; i ++){
        
    		dis[i] = Graph[s][i];
    		if(Graph[s][i] != Inf && i!=s){
        //如果两个城市想通
    			P[i] = s;//修改前驱
    			number[i] = num[s] +num[i];
    			cnt[i] = 1;
    		}
    	}
        vis[s] = 1;//标志被访问过
    
        for(int i = 1; i < n; i ++){
        //查询其余n-1个节点
    		int minx = Inf;
    		int j = 0;
    		int k = -1;
    		while(j < n){
        //找到当前最小的路径
    			if(!vis[j] && dis[j] < minx){
        
    				minx = dis[j];
    				k = j;
    			}
    			j++;
    		}
    		if(k==-1)//没有找到最短路径
                return;
    		vis[k] = 1;//此时标记当前的最短路径
    		for(int i = 0; i < n; i ++){
        //更新dis内容
    		    if(!vis[i] && Graph[k][i] != Inf){
        
    		    	if(Graph[k][i] + dis[k] < dis[i]){
        
    					dis[i] = Graph[k][i] + dis[k];//更新dis内容
    					P[i] = k;//到第i号城市的前驱改为k
    					cnt[i] = cnt[k];//更新到i号城市最短路径的条数也就是到k号城市的最短路径的条数
    					number[i] = num[i] + number[k];//到i号城市的最多数量 = i号本身的数量 + 到k号城市的最多数量
    				}else if(Graph[k][i] + dis[k] == dis[i]){
        
    					if(num[i]+number[k] > number[i]){
        
    						number[i] = num[i]+number[k];
    						P[i] = k;
    					}
    					cnt[i] += cnt[k];
    				}
    			}
    		}
    	}
    }
    int main(){
        
    	cin >> n >> m >> s >> d;
    	init();
    	for(int i = 0; i < n; i ++)
    		cin >> num[i];
    	getGraph();
    	Dijkstra(s, d);
    
        int sum = 0;
        int hs[N];//回溯数组
        int k = 0;
        int di = d;
        while(s!=d){
        
        	hs[k++] = d;
        	d = P[d];
    	}
    	hs[k++] = s;
    	cout << cnt[di] << " " << number[di] << endl;
    	for(int i = k-1; i >= 0;i --){
        
    		printf("%d%c",hs[i],i==0?'\n':' ');
    	}
    
    	return 0;
    }

[https_blog.csdn.net_weixin_43819566_article_details_109068258]: https://blog.csdn.net/weixin_43819566/article/details/109068258