关于算法-数据结构:PAT甲级1003-Emergency

题目粗心：

给出N个城市，M条无向边。每个城市中都有肯定数目的救济小组,所有边的边权均有输出失去,当初给出终点和起点,求从终点到起点的最短门路条数以及最短门路上的救济小组数目之和。如果有多条最短门路,则输入数目之和最大的。

算法思路:

本题须要求解从C1到C2的最短门路上的相干信息,那么很天然联想到用Dijstra算法，此题基本上算的上是模板题目,间接套用Dijstra算法的具体过程即可,这里惟一的不同在于存在优化门路的第二标尺,也即是救济队伍数目。

先交代数据的存储：

这里应用node_weight[1000]示意每一个城市的救济的团队数目，G1000代表每一条路的长度，dis[1000]示意终点C1到所有点的最短距离，visited[1000]为标记拜访数组，num[1000]为终点到起点最优门路的条数，rescue_teams[1000]为终点到起点最优门路上能够携带的最多营救团队数目

Dijkstra过程：

初始化dis[C1] = 0;rescue_teams[C1] = node_weight[C1];num[C1] = 1;而后遍历N次，每次首先寻找到一个没有拜访且间隔终点最短的结点nearest,而后依据nearest结点优化整个图中终点到其余所有节点(没有拜访)的最短距离,当通过nearest能够更短的达到j时，咱们更新最短距离dis[j],num[j],rescue_teams[j],当间隔相等时先更新门路条数num[j],而后判断通过nearest到j的点权是否更大,如果是更新最大点权rescue_teams[j],这里得留神,门路条数num只和最短距离无关.

留神点：

• 1、门路条数num只和最短距离无关，在依据点权作为第二约束条件的时候，无需依据点权来更新。

提交后果：

AC代码：

#include <cstdio>
#include <algorithm>

using namespace std;

int N,M,C1,C2;// 城市数目，路线数目，所在城市，指标城市
int node_weight[1000];// 点权，示意每一个城市的救济的团队数目
int G[1000][1000];// 边权，代表每一条路的长度
int dis[1000];// 终点C1到所有点的最短距离
bool visited[1000];// 标记拜访数组
int num[1000];// 最优门路的条数
int rescue_teams[1000];// 最多营救团队数目

void Dijkstra(){
    fill(dis,dis+1000,0x3fffffff);
    dis[C1] = 0;//终点到终点的最短距离
    num[C1] = 1;// 初始门路条数为1,C1到本身为一条门路
    rescue_teams[C1] = node_weight[C1];// 初始门路的点权之和为C1的点权
    // 循环N次
    for (int i = 0; i < N; ++i) {
        // 首先找到一个间隔C1最近的未拜访的节点
        int nearest = -1,min_dis = 0x3fffffff;
        for (int j = 0; j < N; ++j) {
            if(!visited[j]&&min_dis>dis[j]){
                nearest = j;
                min_dis = dis[j];
            }
        }
        // 没有找到，阐明前面的点不在连通
        if(min_dis==0x3fffffff) return;
        // 找到间隔C1最近的点了，依据nearest更新C1到其余未拜访的点的间隔
        visited[nearest] = true;
        for(int j=0;j<N;++j){
            if(!visited[j]&&G[nearest][j]!=0){
                if(dis[j]>dis[nearest]+G[nearest][j]){
                    dis[j] = dis[nearest]+G[nearest][j];
                    num[j] = num[nearest];
                    rescue_teams[j] = rescue_teams[nearest] + node_weight[j];
                } else if(dis[j]==dis[nearest]+G[nearest][j]){
                    // 门路长度雷同，然而携带的救济团队更多
                    num[j] += num[nearest];
                    if(rescue_teams[j]<rescue_teams[nearest]+node_weight[j]){
                        rescue_teams[j] = rescue_teams[nearest] + node_weight[j];
                    }
                }
            }
        }
    }
}

int main()
{
    scanf("%d %d %d %d",&N,&M,&C1,&C2);
    for (int i = 0; i < N; ++i) {
        scanf("%d",&node_weight[i]);
    }
    for(int i=0;i<M;++i){
        int a,b,length;
        scanf("%d %d %d",&a,&b,&length);
        G[a][b] = G[b][a] = length;
    }
    Dijkstra();
    printf("%d %d",num[C2],rescue_teams[C2]);
    return 0;
}