PAT (Advanced Level) Practice 1003 Emergency

浏览量： 1,031

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:

Sample Output:

2 4

题目大意

有N个城市，城市间有M条路。每个城市都有若干个救援队伍，现在你在C1，需要到C2进行救援，你可以在路上召集当地的救援队伍。求从C1到C2的最短路径的个数，以及你最多可以聚集多少救援队伍。

题目分析

因为要求最短路径的个数，所以必须遍历每一条路径才行。
使用深度优先搜索从C1开始遍历路径即可，记录当前已知的最短长度，用来剪枝。
因为在没遍历完的情况下不知道最短长度的具体值，所以每次发现一个比已知最短长度更短的路径，要把这个长度和在这个路径上可以聚集的救援队伍数保存起来。等得到最终的最短长度后，遍历之前保存的结果，得到最短路径的个数，以及最多可以召集救援队伍的数量。
注意C2本身的救援队伍也要加进答案中。

AC代码

#include <bits/stdc++.h>
using namespace std;
int N, M, C1, C2, minlen = 1 << 30, currentlen = 0, sum;
typedef pair<int, int> p;     //<目的地，边长>
vector<p> v[505];             //图
vector<p> len;                //<最短距离，救援队总数>
int num[505], vis[505] = {0}; //每个城市的救援队伍数量，标志是否访问过
void dfs(int current)         //当前所在城市的标号
{
    if (currentlen > minlen)
        return;
    if (current == C2)
    {
        len.push_back(p(currentlen, sum));
        minlen = currentlen;
        return;
    }
    for (int i = 0; i < v[current].size(); i++)
    {
        if (!vis[v[current][i].first])
        {
            currentlen += v[current][i].second;
            vis[v[current][i].first] = 1;
            sum += num[v[current][i].first];
            dfs(v[current][i].first);
            sum -= num[v[current][i].first];
            vis[v[current][i].first] = 0;
            currentlen -= v[current][i].second;
        }
    }
}

int main()
{
    int i, a, b, l, cnt = 0;
    cin >> N >> M >> C1 >> C2;
    for (i = 0; i < N; i++)
        cin >> num[i];
    for (i = 0; i < M; i++)
    {
        cin >> a >> b >> l;
        v[a].push_back(p(b, l));
        v[b].push_back(p(a, l));
    }
    sum = num[C1];
    dfs(C1);
    for (i = 0; i < len.size(); i++)
    {
        if (len[i].first == minlen)
        {
            cnt++;
            sum = max(sum, len[i].second);
        }
    }
    cout << cnt << " " << sum << endl;
    return 0;
}

打赏赞