PAT (Advanced Level) Practice 10

PAT原题链接： 传送门

1003 Emergency (25 分)

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 c​1, c​2 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 C​1 and C​2​​ , 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

题目大意

题目给出n个城市有m条边使得每两个城市有一条道路相连，每条边有着相应的长度，城市编号由0~n-1，起初每个城市都有一定人数的救援队，现在给出一个出发点c1和终点c2，终点发生火灾后要求你带领出发点的救援队出发救援，沿途召集你经过的城市的救援队参与救援，要求路程尽可能的短，同时如果有多条路一样短则记录下这样的路总数有几条，同时记录下这几条最短的路中你可以沿途召集到的尽可能多的救援队的数量，输出最短路径数和最多可召集的救援队数量

题目分析

典型的求一固定点到其他任意点的最短路径问题，通过dijkstra算法求从c1出发到其他点的最短路径，从c1出发初始化c1到自己的路径长度为0，其余为无穷大，在dist数组中保存从c1点出发到其他各点的最短路径，循环n-1次，每次从中选择一个未走过的最短点，作为下一个要走的点，因为已经将c1到达自己的距离设置为0，所以第一次选择的dist[c1]的点，代表从c1出发，和题意相合（设置man数组放置每个点初始有的救援队，num数组放置到达某个点的最短路径的数量，peo放置到达某个点的最多的救援队）

在具体选择出下一个点k之后，遍历通过该点k是否会使得从c1出发到达其他点j的最短路径缩小，判断可以走之后，还有两种可能性：

• 到j点路径长度缩小 因为j是通过k到达的，所以到j的走法num[j]=num[k]，j的救援队最多是peo[k]+j点原来的人数
• 到j点路径长度不变 那么j可以通过k到达，也可以不通过，num[j]+=num[k],j的救援队最多为max(peo[j],peo[k]+man[j]),通过k到j的人多还是通过别的走法到j的人多，取一个大的值即可

本题代码

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
using namespace std;

const int N=505;
const int M=0x3f3f3f3f;//存放最大值
int vis[N];//是否走过的点
int mat[N][N];//两点之间的距离
int man[N];//某地初始时救援队的数量
int dist[N];//从c1出发到其他地的最短路径
int num[N];//c1到其他点的最短路径的条数
int peo[N];//c1到其他点可召集的救援队数量，在最短路径的基础上
int n,m,c1,c2;

int main(){
    scanf("%d%d%d%d",&n,&m,&c1,&c2);
    for(int i=0;i<n;i++) 
        scanf("%d",&man[i]);
    //初始化
    memset(dist,M,sizeof(dist));
    memset(mat,M,sizeof(mat));
    dist[c1]=0;
    mat[c1][c1]=0;
//  memset(vis,0,sizeof(vis));
//  memset(num,0,sizeof(num));
//  memset(peo,0,sizeof(peo));
    num[c1]=1;          //到达起始点的最短路径初始化为1条
    peo[c1]=man[c1];        //到达起始点的人数最多为man[c1] 
    int a,b,c;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);
        mat[a][b]=c;
        mat[b][a]=c;
    }
//  for(int i=0;i<n;i++)
//      dist[i]=mat[c1][i];
    for(int i=1;i<n;i++){
        int minn=M;
        int k=-1;
        for(int j=0;j<n;j++){
            if(vis[j]==0&&dist[j]<minn){
                minn=dist[j];
                k=j;
            }
        }
        if(k==-1) break;    //剩下的道路已经不通 
        vis[k]=1;
        for(int j=0;j<n;j++){
            if(vis[j]==0&&dist[k]+mat[k][j]<M&&dist[k]+mat[k][j]<dist[j]){
                //有更短的路径
                dist[j]=dist[k]+mat[k][j];
                num[j]=num[k];
                peo[j]=peo[k]+man[j];
            }
            else if(vis[j]==0&&dist[k]+mat[k][j]<M&&dist[k]+mat[k][j]==dist[j]){    //此处的else if开始用成了if 
                num[j]+=num[k];
                peo[j]=max(peo[j],peo[k]+man[j]);
            }
        } 
    }
    printf("%d %d\n",num[c2],peo[c2]);
    return 0;
}