PAT-A1003 Emergency 题目内容及题解

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

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个城市结点及其含有的救援队的数量（点权），以及连接不同城市间的道路信息。题目给出起点和终点，需要找出最短路径的数量，以及所能聚集的最大救援队数量（路径点权和）。

解题思路

1. 按照题目要求进行输入数据的初始化；
2. 求解单源最短路的问题，选用Dijkstra算法；
3. 求解过程中不仅更新最短路径信息，同时需要更新单源最大边权和，和最短路径的数量；
4. 当得到终点的最短路径后即可返回，节约运行时间；
5. 输出所求数据并返回0值。

代码

#include<stdio.h>
#include<string.h>

#define INF 100000000
#define MAXN 510 

int vis[MAXN],d[MAXN],w[MAXN],G[MAXN][MAXN],weight[MAXN],num[MAXN]; 
//访问数组vis,距离d,边权w,图G

int N,M,C1,C2;//边数 路径数 起终点 

void init(){
    int i,j,u,v; 
    scanf("%d%d%d%d",&N,&M,&C1,&C2);//读取
    for(i=0;i<N;i++){
        scanf("%d",&weight[i]);
    }//读点权（救护车数量） 
    for(i=0;i<N;i++){
        vis[i]=0;
        d[i]=INF;
        w[i]=0;
        num[i]=0;
        for(j=0;j<N;j++){
            G[i][j]=INF;
        }
    }//初始化 
    for(i=0;i<M;i++){
        scanf("%d%d",&u,&v);
        scanf("%d",&G[u][v]);
        G[v][u]=G[u][v];//无向图 
    }
    return; 
}//初始化

void Dijkstra(int st){
    int i,j,MIN,u,v; 
    num[st]=1;//起点到起点至少一条路
    d[st]=0;//到自己距离为0
    w[st]=weight[st];//点权为自己
    for(i=0;i<N;i++){
        u=-1;//
        MIN=INF;
        for(j=0;j<N;j++){
            if((vis[j]==0)&&(d[j]<MIN)){
                u=j;
                MIN=d[u];
            }//寻找未被访问过的最小d 
        }
        if(u==-1){
            return;
        }//未找到联通结点退出
        vis[u]=1;//访问u
        for(v=0;v<N;v++){
            if(vis[v]==0&&G[u][v]!=INF){
                if(d[u]+G[u][v]<d[v]){//发现更短路径
                    d[v]=d[u]+G[u][v];//更新距离
                    w[v]=w[u]+weight[v];//更新路径点权和
                    num[v]=num[u];//到达v的最短路径数与到达u的最短路径数相同
                }else if(d[u]+G[u][v]==d[v]){//发现新的最短路径
                    w[v]=(w[v]>w[u]+weight[v]?w[v]:w[u]+weight[v]);//更新最大路径点权和
                    num[v]+=num[u];//最大最短路径数相加
                }
            }
        }
        if(u==C2){
            break;
        } //到达终点，退出 
    }
}
 
int main(){
    init();
    Dijkstra(C1);
    printf("%d %d\n",num[C2],w[C2]);
    return 0;
}

运行结果