A1003 Emergency （Dijkstra算法）

问题

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

思考

这道题是经典的Dijkstra算法的应用，在求最短路径的基础上多求了最短路径条数以及最短路径的最大点权，难度不大（本喵太菜所以还是做了好久）

Dijkstra算法的核心就在于在n次遍历中，（1）遍历所有点根据最短路径增加点集，（2）以及增加完点集后遍历所有点来更新c1到达每个点的最短路径*(dis[u] + e[u][v] < dis[v]) *。而本题中还要求的最短路径条数和在此基础上最大救援队数目，在（2）的里面加一个判断即可实现

代码示例

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, c1, c2;
//邻接矩阵（边和边权） 点权  c1到任意一点的最短长度  c1到任意一点的最短路径的条数  c1到任意一点的救援队数目之和
int e[500][500], weight[500], dis[500], num[500], w[500];
bool visit[510];//作为点的集合
const int inf = 999999;

int main(){

    scanf("%d%d%d%d", &n, &m, &c1, &c2);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &weight[i]);
    }
    fill(e[0], e[0] + 500 * 500, inf);
    fill(dis, dis + 500, inf);

    //初始化邻接矩阵
    int a, b, c;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        e[a][b] = e[b][a] = c;
    }
    //初始化c1
    dis[c1] = 0;
    w[c1] = weight[c1];
    num[c1] = 1;
    for (int i = 0; i < n; i++)
    {
        int u = -1;
        int minn = inf;
        //遍历所有点，找到到c1路径最短的那个点，加入到点集，直到遍历完所有点为止
        for (int j = 0; j < n; j++)
        {   //从c1开始
            if(visit[j] == false && dis[j] < minn){
                u = j;
                minn = dis[j];
            }
        }
        if (u == -1) break;
        visit[u] = true;
        //在点集加了一个点之后，遍历所有点，更新c1到所有点的最短路径
        for (int v = 0; v < n; v++)
        {   //如果新点与该点有边
            if (visit[v] == false && e[u][v] != inf)
            {   //如果新点到任一点的距离比原来小，就更新dis
                if (dis[u] + e[u][v] < dis[v])
                {
                    dis[v] = dis[u] + e[u][v];
                    num[v] = num[u]; //c1到达新点的最短路径条数应该与与他联通的v点相同
                    w[v] = w[u] + weight[v];
                }
                else if (dis[u] + e[u][v] == dis[v])
                {
                    num[v] = num[v] + num[u];//新点不变，v点加上刚联通的u点的最短路径条数
                    if (w[u] + weight[v] > w[v])//如果这条路上的救援队数目更多，就更新
                    {
                        w[v] = w[u] + weight[v];
                    }
                }

            }

        }

    }
    printf("%d %d",num[c2],w[c2]);
    return 0;
}

(解题时参考了柳婼大大的代码 有兴趣可以去看一下 -> 柳婼のBlog)