PAT甲级emergency

PAT甲级emergency题解

原题及翻译

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.

翻译

> 作为一个城市中一支紧急救援队的领导者，你拿到了一张城市的特殊地图。 地图中展现了通过一些路被联系起来的分散城市。每个城市的救援队伍数量和每两个城市之间的路径长度都被标注在了地图上。当你收到来自其他城市的救援呼叫时，你的工作室带领你的队员尽可能块的感到目的地，同时尽可能多的寻求帮助。

题解

这题做过中文版的，太长时间没刷题了迪杰斯特拉算法都有点模糊了，从网上找了个代码顺便复习一下。感觉这个代码写的比我的清晰简洁很多。可以当做模板学习一下
基本思路就是迪杰斯特拉算法找出最短路的条数,以及保证路径最短的前提下能召集的最多救援队伍数目。

程序

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, C1, C2;
    cin >> n >> m >> C1 >> C2;
    //点权，也就是每个城市救援队的数量
    vector<int> weight(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> weight[i];
    }
    //边，无路用无限大表示
    vector<vector<int>> edge(n, vector<int>(n, INT_MAX));
    //到某个点的最短路径
    vector<int> dis(n, INT_MAX);
    //到某个点的最小路径条数
    vector<int> roads(n, 0);
    //到某个点最多可以召集的救援队数量
    vector<int> teams(n, 0);
    //访问标记
    vector<bool> visit(n, false);

    //初始化边权值表
    int c1, c2, L;
    //输入
    for (int i = 0; i < m; i++)
    {
        cin >> c1 >> c2 >> L;
        edge[c1][c2] = edge[c2][c1] = L;
    }
    //出发点长度为0
    dis[C1] = 0;
    //出发点救援队数
    teams[C1] = weight[C1];
    //一条路到出发点
    roads[C1] = 1;
    //迪杰斯特拉
    for (int i = 0; i < n; ++i)
    {
        //在未访问的点钟寻找能到达的最短的那条
        int u = -1, minn = INT_MAX;
        for (int j = 0; j < n; j++)
        {
            if (visit[j] == false && dis[j] < minn)
            {
                u = j;
                minn = dis[j];
            }
        }
        //找不到就结束
        if (u == -1)
            break;
        //访问这个点
        visit[u] = true;
        //更新点
        for (int v = 0; v < n; v++)
        {
            //没有访问并且和u点有路
            if (visit[v] == false && edge[u][v] != INT_MAX)
            {
                //新路优于旧路
                if (dis[u] + edge[u][v] < dis[v])
                {
                    dis[v] = dis[u] + edge[u][v];
                    roads[v] = roads[u];
                    teams[v] = teams[u] + weight[v];
                }
                //新旧路长度相同
                else if (dis[u] + edge[u][v] == dis[v])
                {
                    //路径条数增加
                    roads[v] = roads[v] + roads[u];
                    //队伍数量更多
                    if (teams[u] + weight[v] > teams[v])
                    {
                        //更新队伍数量
                        teams[v] = teams[u] + weight[v];
                    }
                }
            }
        }
    }
    cout << roads[C2] << " " << teams[C2] << endl;
    return 0;
}