1003 Emergency(25 分)

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;
}
上一篇:1003 Emergency (25 分)


下一篇:Linux下部署Java应用程序