[数据结构与算法]1003 Emergency (25 分)

1003 Emergency (25 分)

题目大意

n个城市m条路，每个城市有救援小组，所有的边的边权已知。给定起点和终点，求从起点到终点的最短路径条数以及最短路径上的救援小组数目之和。如果有多条就输出点权（城市救援小组数目）最大的那个

基本思路

因为这里不需要我们输出具体的最短路径，所以直接用Dij算法解决即可，参考算法笔记的模板即可解决。

代码

具体数据结构和详细代码的设计请看注释：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=510;
const int INF=1000000000;

int n,m,s,e;//顶点数，边数，起始顶点，终止顶点
int G[MAXN][MAXN];//邻接矩阵存储这一张图。初始化每个元素为INF，再从题目中读入边的距离
int d[MAXN];//起点s到顶点u的最短距离。初始化d[s]=0,其余d[u]均为INF。
bool vis[MAXN]={false};//顶点在V中还是在S中
int weight[MAXN];//点权。直接由题目读入
int w[MAXN];//起点s到顶点u的最大点权之和。初始化w[s]=weight[s],其余w[u]均为0。
int num[MAXN];//起点s到顶点u的最短路径条数。初始化num[s]=1,其余num[u]均为0。

void Dijkstra(){
    for(int i=0;i<n;i++){//循环n次，把n个顶点加入S
        //找出当前未访问结点中距离起点最近的顶点
        int u=-1,MIN=INF;//u为未访问顶点里离起点最近的顶点编号，MIN为最短距离
        for(int j=0;j<n;j++){
            if(vis[j]==false&&d[j]<MIN){
                u=j;
                MIN=d[j];
            }
        }
        //看看是否找到了这样的顶点
        if(u==-1) return;
        else vis[u]=true;
        //开放从这个顶点出发的所有边，看看在V-S中的最短距离等信息能否被进一步优化
        for(int v=0;v<n;v++){
            if(vis[v]==false&G[u][v]!=INF){
                if(d[u]+G[u][v]<d[v]){
                    d[v]=d[u]+G[u][v];
                    w[v]=w[u]+weight[v];
                    num[v]=num[u];
                }
                else if(d[u]+G[u][v]==d[v]){
                    if(w[u]+weight[v]>w[v]){
                        w[v]=w[u]+weight[v];
                    }
                    num[v]=num[v]+num[u];//最短路径的条数和点权无关，必须写在外面
                }
            }
        }
    }
}

int main(){
    //读入并初始化所有的数据
    scanf("%d%d%d%d",&n,&m,&s,&e);
    fill(d,d+MAXN,INF);
    d[s]=0;
    for(int i=0;i<n;i++){
        scanf("%d",&weight[i]);
    }
    fill(w,w+MAXN,0);
    w[s]=weight[s];
    fill(num,num+MAXN,0);
    num[s]=1;
    fill(G[0],G[0]+MAXN*MAXN,INF);
    for(int i=0;i<m;i++){
        int u,v,edgeweight;
        cin>>u>>v>>edgeweight;
        G[u][v]=G[v][u]=edgeweight;//无向图，对角线两侧均需赋值
    }
    //Dijkstra函数
    Dijkstra();
    //输出
    printf("%d %d\n",num[e],w[e]);  
    return 0; 
}