1003 Emergency（25 分）

借鉴以下两博客：

https://blog.csdn.net/qq_41658889/article/details/82492985

****Dijkstra算法****https://blog.csdn.net/yalishadaa/article/details/55827681

#include<iostream>
using namespace std;

int main(){
    const int MAX = 0x7fffffff;
    int N, M, c1, c2;
    cin >> N >> M >> c1 >> c2;
    int graph[N][N], dist[N], citynum[N], vis[N] = {0};     //graph--地图，dist--距离，citynum--该城市救援人员，vis--标记
    for(int i = 0;i < N;i++){
        dist[i] = MAX;
        for(int j = 0;j < N;j++){
            graph[i][j] = -1;
        }
    }
    for(int i = 0;i < N;i++){
        cin >> citynum[i];
    }
    for(int i = 0;i < M;i++){
        int x, y, z;
        cin >> x >> y >> z;
        graph[x][y] = z;
        graph[y][x] = z;
    }
    
    if(N == 0){
        cout << "0 0"<<endl;
        return 0;
    }
    if( c1 == c2){
        cout << "1 " << citynum[c1] << endl;
        return 0;
    }
    
    //将出生地放入容器
    int rec[N][2] = {0};        //[可能的次数，最大救援人员]
    rec[c1][0] = 1;
    rec[c1][1] = citynum[c1];
    vis[c1] = 1;
    dist[c1] = 0;
    int cen = c1;
    while(1){
        //1.找到cen相邻的点
        for(int i = 0;i < N;i++){
            if(vis[i] == 0 && graph[cen][i] != -1){
                if(dist[i] > graph[cen][i] + dist[cen]){
                    dist[i] = graph[cen][i] + dist[cen];
                    rec[i][0] = rec[cen][0];
                    rec[i][1] = citynum[i] + rec[cen][1];
                }
                else if(dist[i] == graph[cen][i] + dist[cen]){
                    rec[i][0] += rec[cen][0];
                    rec[i][1] = rec[i][1] > rec[cen][1] + citynum[i]?rec[i][1] : rec[cen][1] + citynum[i];
                }
            }
        }
        //2.找下一个节点
        int MIN = MAX;
        for(int i = 0;i < N;i++){
            if(vis[i] == 0 && MIN > dist[i]){
                MIN = dist[i];
                cen = i;
            }
        }
        vis[cen] = 1;
        if(c2 == cen)break;
    }
    cout << rec[c2][0] << " " << rec[c2][1] << endl;
    return 0;
}