PAT甲级 1003 Emergency题解

描述

该题目是英文的，在天梯赛练习集中有一道类似的中文题目：

https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840

如图：

该题目要求输出城市c1-c2的最短路径的条数，以及在多条最短路径上最多所能集结的救援队的数量。

符号说明

cost[i]：从起点到i的最短路径的值

graph：邻接矩阵

min_pos：新加入节点的下标

res_num[i]：到该节点时一共集结的救援队数量

road_num[i]：到节点i的最短路径条数

team_num[i]：某个节点原本具有的救援队数目

解题思路

该问题是最短路径问题，需要借助Dijkstra算法，但是这个题不仅需要找到最短路径，还要找到条数以及救援队的数量。

具体解法见以下代码：

if graph[min_pos][j]+cost[min_pos]<cost[j]:
    road_num[j] = road_num[min_pos]
    res_num[j] = res_num[min_pos]+team_num[j]
    cost[j] = graph[min_pos][j]+cost[min_pos]
elif graph[min_pos][j]+cost[min_pos]==cost[j]:
    road_num[j] += road_num[min_pos]
  res_num[j] = max(res_num[min_pos]+team_num[j],res_num[j])

该部分代码大意是，如果发现了更小的cost，更新cost，同时将节点的救援队数量更新为自己拥有的和新加入节点的，最短路径条数更新为新加入节点的。否则，最短路径条数要加上新加入节点的，且救援队的数目是当前已经有的和若从新节点来该节点应该有的数目中的最大值。

代码

以下给出了两个版本的代码，大意是一样的，建议用c++，python只是练习用。

#include<iostream>
#include<vector>
#define INF 0x3f3f3f3f
using namespace std;

vector<int> cost(500,INF);//到某个点的最短距离
bool visit[500] = {0}; //一个点是否在集合中
vector<vector<int> >graph(500,vector<int>(500,INF)); //邻接矩阵
vector<int>team_num(500,0);//每个点拥有的队伍数
vector<int>res_num(500,0);//到达i点的救援队数量
vector<int>raod_num(500,0);//到达i点多少条不同的道路

void dijkstra(int first,int n)
{
    //初始化第一个点的信息
    raod_num[first] = 1;
    res_num[first] = team_num[first];
    cost[first] = 0;
    visit[first] = 1;
    //初始化每个点的救援队数量
    for(int i = 0;i < n;i++)
    {
        cost[i] = graph[first][i];
        if(cost[i]!=INF)
        {
            raod_num[i] = 1;
            //与原点直接连接
            if(i!=first)
                res_num[i] = team_num[i]+team_num[first];
        }
        else
        {
            //与原点不直接连接
            res_num[i] = team_num[i];
        }

    }
    //在集合中加入其它的点
    for(int i = 1;i < n;i++)
    {
        int min = INF+1;
        int min_pos = 0;
        //找到未加入集合，且离原点最近的点
        for(int j = 0; j < n;j++)
        {
            if(!visit[j]&&cost[j]<min)
            {
                min = cost[j];
                min_pos = j;
            }
        }
        visit[min_pos] = 1;
        //修改相关的路径
        for(int j = 0;j < n;j++)
        {
            if(j==min_pos)  continue;//不加这句话会导致错误的执行else if语句
            if(graph[min_pos][j]+cost[min_pos]<cost[j])
            {
                cost[j] = graph[min_pos][j]+cost[min_pos];
                raod_num[j] = raod_num[min_pos];
                res_num[j] = res_num[min_pos]+team_num[j];
            }
            else if(graph[min_pos][j]+cost[min_pos]==cost[j])
            {
                raod_num[j] += raod_num[min_pos];
                res_num[j] = max(res_num[j],res_num[min_pos]+team_num[j]);
            }
        }
    }
}
int main()
{
    int n,m,a,b;
    //输入输出重定向语句，在测试时使用，提交时注释掉
    //freopen("1.txt","w",stdout);
    //freopen("2.txt","r",stdin);
    cin>>n>>m>>a>>b;
    for(int i = 0;i < n;i++){
        cin>>team_num[i];
        graph[i][i] = 0;
    }
    for(int i = 0;i < m;i++)
    {
        int t1,t2,dis;
        cin>>t1>>t2>>dis;
        graph[t1][t2] = graph[t2][t1] = dis;
    }
    dijkstra(a,n);
    cout<<raod_num[b]<<" "<<res_num[b]<<endl;
    return 0;
}

python版本

INF = 0x3f3f3f#初始化一个特别大的值
n,m,c1,c2 = [int(i) for i in input().split()]
#输入队伍数
team_num = [int(i) for i in input().split()]
#初始化一些变量
graph = []
res_num = [0]*n
visit = set()#标记是否被访问过
cost = [INF]*n#各点到原点的距离
road_num = [0]*n#到每个点有几条路可以走
#邻接矩阵的初始化
for i in range(n):
    graph.append([INF]*n)
    graph[i][i] = 0
#输入邻接矩阵中的数据
for i in range(m):
    a,b,dis = [int(j) for j in input().split()]
    graph[a][b] = graph[b][a] = dis
def dijkstra():
    #初始化
    visit.add(c1)
    road_num[c1] = 1
    res_num[c1] = team_num[c1]
    for i in range(n):
        cost[i] = graph[c1][i]
        if cost[i]!=INF and cost[i]!=0:
            res_num[i] = team_num[i]+res_num[c1]
            road_num[i] = 1
        else:
            res_num[i] = team_num[i]
    #加入新的节点
    for i in range(n-1):
        minnum = INF+1
        min_pos = 0
        for j in range(n):
            if j not in visit and cost[j]<minnum:
                minnum = cost[j]
                min_pos = j
        visit.add(min_pos)
        for j in range(n):
            #注意j==min_pos
            if j==min_pos:
                continue
            if graph[min_pos][j]+cost[min_pos]<cost[j]:
                road_num[j] = road_num[min_pos]
                res_num[j] = res_num[min_pos]+team_num[j]
                cost[j] = graph[min_pos][j]+cost[min_pos]
            elif graph[min_pos][j]+cost[min_pos]==cost[j]:
                road_num[j] += road_num[min_pos]
                res_num[j] = max(res_num[min_pos]+team_num[j],res_num[j])
dijkstra()
print(road_num[c2],res_num[c2])