【PTA】城市间紧急救援

た入场券 2023-07-01 13:55 6阅读 0赞

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

#### 输入格式: ####

输入第一行给出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

#### C++ AC ####

#include<iostream>
    #include <bits/stdc++.h>
    #define Inf 0x3f3f3f3f
    using namespace std;
    int n,m,s,d;
    int mp[505][505];//存放路径
    int pace[505];//最短路径条数
    int vis[505];//标记是否访问过
    int num[505];
    int sum[1001];//
    int pre[1001];//前驱路径
    
    void Dijkstra(){
        
    	pace[s]=vis[s]=1;
    
    	for(int i=0;i<n-1;i++){
        
    		int MIN=Inf,f=-1;
    		/***找距离源点最近的，且未被访问**/
    		for(int j=0;j<n;j++){
        
    			if(!vis[j]&&mp[s][j]<MIN){
        
    				MIN=mp[s][j];
    				f=j;
    			}
    		}
    		if(f==-1) break;
    		vis[f]=1;
    
    		for(int j=0;j<n;j++){
        
    			if(!vis[j]&&mp[s][j]>mp[s][f]+mp[f][j]){
        
    				mp[s][j]=mp[s][f]+mp[f][j];
    				pre[j]=f;
    				pace[j]=pace[f];
    				sum[j]=sum[f]+num[j];
    			}
    			else if(!vis[j]&&mp[s][j]==mp[s][f]+mp[f][j]){
        
    				pace[j]+=pace[f];
    				if(sum[j]<sum[f]+num[j]){
        
    					pre[j]=f;
    					sum[j]=sum[f]+num[j];
    				}
    			}
    		}
    	}
    }
    int main(){
        
    	int city1,city2;
    	cin>>n>>m>>s>>d;
    	memset(vis,0,sizeof vis);
    	for(int i=0;i<n;i++)
    		for(int j=0;j<n;j++)
    			if(i!=j) mp[i][j]=mp[j][i]=Inf;
    	for(int i=0;i<n;i++){
        
    		cin>>num[i];
    		sum[i]=num[i];
    		pace[i]=1;
    	}
    	for(int i=0;i<m;i++){
        
    		cin>>city1>>city2;
    		cin>>mp[city1][city2];
    		mp[city2][city1]=mp[city1][city2];
    	}
    	Dijkstra();
    	cout<<pace[d]<<" "<<sum[d]+num[s]<<endl;
    
    
    	int road[1001];
    	int cur=d,cnt=0;
    	while(pre[cur]!=0){
        
    		road[cnt++]=pre[cur];
    		cur=pre[cur];
    	}
    	//输出
    	cout<<s;
    	for(int i=cnt-1;i>=0;i--)
    		cout<<" "<<road[i];
    	cout<<" "<<d;
    	return 0;
    }