PAT-A-1003 Emergency (25分) C/C++实现（最短路径，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

• 题目大意：

  给出编号为0 ~ n - 1 的n个城市，城市之间有m条路，每条路的两个端点和长度已知；每个城市有一些救援小组，数目已知。现给定起点和终点，求从起点到终点最短路径的条数，以及在最短路径上可以到达的救援小组数目之和的最大值。

• 思路：
  1. 用Dijkstra算法计求得最短路径；
  2. 注意最后需要输出的是最短路径的数量而非距离；

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 0xfffffff
using namespace std;
struct Node
{
    int next, dis; 
};
vector <Node> city[500]; //记录相邻城市之间的路程
int num_rescue[500];//记录每个城市的救援组的数量
int min_dist[500];//记录起点到各个城市的最短距离
int num_mindist_route[500] = {0};//记录起点到各个城市的距离最短路径的条数
int max_rescue[500] = {0};//记录起点到各个城市可以召集的最多救援人数
bool mark[500] = {0};
int n, m, s, d;
void Dijkstra(int newp)
{
    if (newp == d)
    {
        return;
    }
    for (int i = 0; i < city[newp].size() ; i++) //遍历与当前点直接相邻的点，更新最短路径的长度、数量，和最大救援队数目
    {
        int next = city[newp][i].next, dis = city[newp][i].dis;
        if (mark[next] == true)
        {
            continue;
        }
        if (min_dist[next] == -1 || min_dist[next] > min_dist[newp] + dis)
        {
            min_dist[next] = min_dist[newp] + dis;
            num_mindist_route[next] = num_mindist_route[newp];
            max_rescue[next] = max_rescue[newp] + num_rescue[next];
        }
        else if (min_dist[next] == min_dist[newp] + dis)
        {
            num_mindist_route[next] += num_mindist_route[newp]; //如果距离相等，则起点到当前城市的距离最短路径的条数为两者之和
            max_rescue[next] = max(max_rescue[next], max_rescue[newp] + num_rescue[next]);
        }
    }
    int mindis = 0xfffffff, index;
    for (int i = 0; i < n; i++) //在剩余未被标记的点中，选出与起点距离最近的点
    {
        if (mark[i] == true || min_dist[i] == -1)
        {
            continue;
        }
        if (min_dist[i] < mindis)
        {
            mindis = min_dist[i];
            index = i;
        }
    }
    mark[index] = true;
    Dijkstra(index);
}
int main()
{
    cin >> n >> m >> s >> d;
    for (int i = 0; i < n; i++)
    {
        cin >> num_rescue[i];
    }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        Node temp;
        cin >> a >> b >> temp.dis;
        temp.next = b;
        city[a].push_back(temp);
        temp.next = a;
        city[b].push_back(temp);
    }
    fill(min_dist, min_dist + n, -1);
    mark[s] = true, min_dist[s] = 0, max_rescue[s] = num_rescue[s], num_mindist_route[s] = 1;
    Dijkstra(s);
    cout << num_mindist_route[d] << ' ' << max_rescue[d];
    return 0;
}