PAT 1003 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₁ and C₂ - 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₁, c₂ 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₁ to C₂.

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between C₁ and C₂, 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:

Sample Output:

2 4

题目大意

渣翻：身为城市紧急救援队的领导，你手握一张城市的特殊地图，地图上画了一些由路连接起来的分散的城市，并标记出了每座城市的救援队的数量和每两座城市间的路的长度。当某一城市发出紧急请求时，你需要尽快带领你的队员们就位，同时召集尽可能多的支援。输入保证C₁到C₂间至少存在一条路径。

输入的第一行包含4个正整数：N表示城市的数量（所有城市从0到N-1编号），M表示路的数量，C₁和C₂分别表示你所在的城市和需要你前往救援的城市。输入的下一行包含N个整数，第i个数表示编号为i的城市的救援队个数。之后的M行中，每行用c₁、c₂和L三个整数表示一条从城市c₁到c₂的一条长度为L的路。
输出一行两个整数，中间用空格隔开。其中第一个整数代表C₁到C₂间不同的最短路径条数，第二个整数代表能够召集到的最大的救援队数量。

题解

求带权（边权和点权，权值非负）无向图的最短路径条数，以及路径最短时经过的点的点权和最大值。
采用Dijkstra算法，并额外维护表示从起点到某点的路径条数及最大点权和的数组。

样例输入

算法开始时数据初始化为下表：

city_index	visited	dis	roads_num	teams_num
0	false	0	1	1
1	false	INT_MAX	0	0
2	false	INT_MAX	0	0
3	false	INT_MAX	0	0
4	false	INT_MAX	0	0

首先找到距离起点最近，即dis最小的点（第一次循环必为起点），将该点的visited置为true。然后从该点出发，查找未被访问过且与该点连通的点，判断是否需要进行松弛操作或更新roads_num和teams_num。
第一次循环后，各变量的内容如下：

city_index	visited	dis	roads_num	teams_num
0	true	0	1	1
1	false	1	1	3
2	false	2	1	2
3	false	1	1	6
4	false	INT_MAX	0	0

可见c₁、c₂和c₃分别进行了一次松弛操作，并更新了相关的变量值。

第二次循环找到的距起点最近的点为c₁，与c₁连通且未被访问过的点只有c₂，而由起点经c₁到c₂的距离与由起点直接到c2的距离相同，且经c₁到达c₂时经过的点的点权和更大，此时需更新c₂的roads_num和teams_num。更新后各变量内容如下表：

city_index	visited	dis	roads_num	teams_num
0	true	0	1	1
1	true	1	1	3
2	false	2	2	4
3	false	1	1	6
4	false	INT_MAX	0	0

再次循环，此时从c₃出发寻找到可以扩展的点c₄，并将c₄的各项数值更新。

city_index	visited	dis	roads_num	teams_num
0	true	0	1	1
1	true	1	1	3
2	false	2	2	4
3	true	1	1	6
4	false	2	1	9

此时发现距离起点最近的点为c₂，说明起点到c₂的最短路径长已经找到，即dis[2]。跳出循环按要求输出roads_num[c₂]和teams_num[c₂]即可。
Ｃ语言代码如下：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<limits.h>
#define true 1
#define false 0
#define max(a,b) (((a) > (b)) ? (a) : (b))

int N, M, origin, dest;
int edge[501][501];

int main(){
    int c1, c2, L;
    scanf("%d %d %d %d", &N, &M, &origin, &dest);
    int *nums = (int*) malloc(sizeof(int) * N);
    for(int i = 0;i < N;i++)
        scanf("%d", nums + i);
    for(int i = 0;i < N;i++)
        for(int j = 0;j < N;j++)
            edge[i][j] = INT_MAX;
    for(int i = 0;i < M;i++){
        scanf("%d %d %d", &c1, &c2, &L);
        edge[c1][c2] = edge[c2][c1] = L;
    }

    unsigned char *visited = malloc(N);                         //存储是否访问过某点
    unsigned int *roads_num = malloc(sizeof(unsigned int) * N); //存储起点到某点的路径数量
    unsigned int *teams_num = malloc(sizeof(unsigned int) * N); //存储起点到某点的最大点权和
    unsigned int *dis = malloc(sizeof(unsigned int) * N);       //存储起点到某点的最短距离
    memset(visited, 0, N);
    memset(roads_num, 0, sizeof(unsigned int) * N);
    memset(teams_num, 0, sizeof(unsigned int) * N);
    for(int i = 0;i < N;i++) dis[i] = INT_MAX;
    roads_num[origin] = 1;
    dis[origin] = 0;
    teams_num[origin] = nums[origin];
    while(true){
        int current, minn = INT_MAX;
        for(int i = 0;i < N;i++){
            if(!visited[i] && dis[i] < minn){   //找到当前未访问过的离起点最近的点
                current = i;
                minn = dis[i];
            }
        }
        if(current == dest) break;
        visited[current] = true;
        for(int i = 0;i < N;i++){
            if(!visited[i] && edge[current][i] != INT_MAX){
                if(dis[current] + edge[current][i] < dis[i]){   //松弛
                    dis[i] = dis[current] + edge[current][i];
                    roads_num[i] = roads_num[current];
                    teams_num[i] = teams_num[current] + nums[i];
                }
                else if(dis[current] + edge[current][i] == dis[i]){
                    roads_num[i] += roads_num[current];
                    teams_num[i] = max(teams_num[i], teams_num[current] + nums[i]);
                }
            }
        }
    }
    printf("%d %d\n", roads_num[dest], teams_num[dest]);
    // free(nums);
    // free(visited);
    // free(roads_num);
    // free(teams_num);
    return 0;
}

PAT 1003 Emergency