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

Output Specification

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

题解

Dijkstra算法流程+一些小改动

1. 初始化所图参数：①城市节点权重为城市的救援队数city[CITY]；②边权重为距离，不可达为无限大road[CITY][CITY]；③起点到各个城市距离为无限大，起点到起点距离为0minlen[CITY]；
2. 新建两个数组same[CITY]和sum[CITY] 分别表示起点至终点最短路径个数，和尽可能获得最大救援队数量；
3. 每次寻找到minlen中值最小的节点k，并且进行Dij计算；
4. 如果minlen[i]被更新，则同时更新same[i]=same[k]，因为same存储相同路径长度数量；同时更新 sum[i]=sum[k]+city[i]；
5. 若road[i][k] + minlen[k] == minlen[i]，表示出现了相同最短路径，更新same[i] += same[k]；同时更新可获取最大救援队数量(提前做判断)sum[i] = sum[k] + city[i]

示例输入图示：

Code

#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

const int CITYNUM = 500;
const int INF = 10000;

int city[CITYNUM];
int road[CITYNUM][CITYNUM];
bool visited[CITYNUM];
int same[CITYNUM] = { 0 };
int sum[CITYNUM] = { 0 };
int minlen[CITYNUM];

void Dij(int source, int dest, int n)
{
    int k, t, mm, next;
    int cur = source;
    int count = 0;

    same[cur] = 1;
    minlen[cur] = 0;
    sum[cur] = city[cur];

    while (count < n - 1)
    {
        mm = INF;
        for (int i = 0; i < n; i++)
        {
            // 找到一个未处理节点
            if (!visited[i] && minlen[i] < mm)
            {
                mm = minlen[i];
                k = i;
            }
        }

        visited[k] = true;
        // 遍历所有剩余为访问节点，满足road[i][cur]+minlen[cur] < minlen[i]
        for (int i = 0; i < n; i++)
        {
            if (visited[i] || road[k][i] == INF) continue;
            t = road[i][k] + minlen[k];
            if (t < minlen[i])
            {
                minlen[i] = t;
                same[i] = same[k];
                sum[i] = sum[k] + city[i];
            }
            else if (t == minlen[i])
            {
                same[i] += same[k];
                if (sum[i] < sum[k] + city[i])
                    sum[i] = sum[k] + city[i];
            }
        }
        
        count++;
    }
}

int main()
{
    memset(minlen, INF, sizeof(minlen));
    memset(road, INF, sizeof(road));

    int n, m, sc, dc;
    cin >> n >> m >> sc >> dc;
    int i;
    for (int i = 0; i < n; i++) cin >> city[i];
    int c1, c2;
    for (int i = 0; i < m; i++)
    {
        cin >> c1 >> c2;
        cin >> road[c1][c2];
        road[c2][c1] = road[c1][c2];
    }
    if (sc == dc)
        cout << 1 << " " << city[sc] << endl;
    else
    {
        Dij(sc, dc, n);
        cout << same[dc] << " " << sum[dc] << endl;
    }
}