1003 Emergency C++

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 c1​, c2​ 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 C1​ and C2​, 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

题意：

构造一个无向连通图，求单源最短路径。Dijistra。

分析：

在计算c1到c2的边的权重最小的一条路径的时候，本题还要求找到所有最短的路径，但是不需要记录每条路径，只需要输出个数，用ways数组来记录起点到达终点的最短路径条数（ways数组也包含了起点到达其他顶点的最短路径条数）。另外，这道题还需要记录起点到终点的最大点权和，用totalRescue数组记录起点到达每一个顶点的累积最大点权。Dijistra算法的思路是这样的，用一个顶点集vist来表示已访问的节点，用一个dist数组来记录顶点到达每一个顶点的最短路径值。每次从dist数组里找一个未访问的dist值最小的节点，这个值就是源点到该顶点的最短路径，然后将其标记为已访问，然后需要比较通过新加入的节点到达其他点的路径是否比从源点直接到达更近，如果更近，则更新这些顶点在dist数组里的值。

① 比较 dist[index] + map[index][j] < dist[j]，如果满足，则说明通过新加入的节点到达j顶点，比通过原来的路径到达j顶点更短，此时需要更新dist[j]，即dist[j] = dist[index] + map[index][j]，但此题还需要更新其他的值，因为最短路径变了，到达j点的路径的点权总和也要跟着变，即totalRescue[j] = totalRescue[index] + weight[j]，到达j点的最短路径总数也要跟着变，即和新加入的index节点一致， ways[j] = ways[index];

②若dist[index] + map[index][j] == dist[j]，说明到达j点的最短路径有多条，即经过新加入的index节点与直接到达j点是一样的。需要更新ways数组，即ways[j] += ways[index]，然后更新路径中最大的点权值，判断新加入的路径的点权是否大于原来的，totalRescue[index] + weight[j] > totalRescue[j]，如果是，则更新，即totalRescue[j] = totalRescue[index] + weight[j]。

代码：

//
// Created by yaodong on 2023/7/5.
//

#include "iostream"
#include "cstring"

//#define INF 0xfffff
const int INF = 0xffffff;
int main() {
    int n, m, c1, c2;
    std::cin >> n >> m >> c1 >> c2;
    int weight[n];
    for (int i = 0; i < n; ++i) {
        std::cin >> weight[i];
    }
    int begin, end, distance;
    int map[n][n];
    std::fill(map[0], map[0]+n*n, INF);

    for (int i = 0; i < m; ++i) {
        std::cin >> begin >> end >> distance;
        map[begin][end] = distance;
        map[end][begin] = distance;
    }


    int totalRescue[n];     // 记录点的最大权，也就是城市能提供的最大救援队个数
    int visit[n];           // 标记节点是否访问
    int ways[n];            // 记录从起点到每个节点的最短路径条数
    int dist[n];            // 记录从起点到每个节点的最短路径
    memset(visit, 0, sizeof(visit));
    memset(totalRescue, 0, sizeof(totalRescue));
    memset(ways, 0, sizeof(ways));
    std::fill(dist, dist+n, INF);
//    printf("helolo %d\n", dist[1]);

    //Dijistra
    dist[c1] = 0;
    totalRescue[c1] = weight[c1];
    ways[c1] = 1;

    for (int i = 0; i < n; ++i) {
        int index = -1, min = INF;
        // 每次找到距离最短的最小的未访问过的点，最开始是起点c1。
        for (int j = 0; j < n; ++j) {
            if(visit[j] == 0 && dist[j] < min){
                index = j;
                min = dist[j];
            }
        }
        if(index == -1) break;      //如果节点均访问过，则退出
        visit[index] = 1;        //将要访问的节点标记已访问
        
        /* *
         * 算法的思路是这样的，每次从dist数组里找一个最小的，这个值就是源点到该顶点的最短路径
         * 并把该点加入到已访问节点的集合当中，然后需要看新加入的顶点是否可以到达其他顶点，并
         * 比较通过该顶点到达其他点的路径是否比之前的路径直接到达短，如果是，则替换这些顶点在
         * dist数组里的值。
         */
        for (int j = 0; j < n; ++j) {
            if(visit[j] == 0 && map[index][j] != INF){
                if(dist[index] + map[index][j] < dist[j]){
                    dist[j] = dist[index] + map[index][j];
                    totalRescue[j] = totalRescue[index] + weight[j];
                    ways[j] = ways[index];
                }else if(dist[index] + map[index][j] == dist[j]){
                    ways[j] += ways[index];
                    if(totalRescue[index] + weight[j] > totalRescue[j])
                        totalRescue[j] = totalRescue[index] + weight[j];
                }
            }
        }
    }
    printf("%d %d", ways[c2], totalRescue[c2]);
}