[PAT]-L2-001 紧急救援 （25 分)-dijkstra

L2-001.png

分析

这是一道dijkstra的变式题，在求最短路径的基础上，求获得的最大救援数量
写的时候的主要坑点就在于计算有多少条最佳路径。

if(dis[v]>dis[u]+map[u][v]){
  roadnum[v]=roadnum[u];
}
else if(dis[v]==dis[u]+map[u][v]){
  roadnum[v]+=roadnum[u];
}

AC代码

#include<iostream>
#include<vector>
using namespace std;
#define maxn 500
#define inf 0x3f3f3f3f
int n,m,st,ed;

int map[maxn][maxn];
int dis[maxn];
int book[maxn];
int Maxteam[maxn];
int team[maxn];
int pre[maxn];
int roadnum[maxn];

void printPath(int v){
    if(v==st){
        cout<<v;
        return;
    }
    printPath(pre[v]);
    cout<<" "<<v;
}


void dijkstra(int x){
    for(int i=0;i<n;i++){
        dis[i]=inf;
        Maxteam[i]=inf;
    }
    dis[x]=0;
    Maxteam[x]=team[x];
    roadnum[x]=1;
    
    for(int i=0;i<n;i++){
        int min=inf,u=-1;
        for(int j=0;j<n;j++){
            if(book[j]==0 && min>dis[j]){
                min=dis[j];
                u=j;
            }
        }
        if(u==-1) break;
        book[u]=1;
        for(int v=0;v<n;v++){
            if(book[v]==0 && map[u][v]<inf ){
                if(dis[v]>dis[u]+map[u][v]){
                    dis[v]=dis[u]+map[u][v];
                    pre[v]=u;
                    roadnum[v]=roadnum[u];
                    Maxteam[v]=Maxteam[u]+team[v];
                    
                }else if(dis[v]==dis[u]+map[u][v]){
                    roadnum[v]+=roadnum[u];
                    if(Maxteam[v]<Maxteam[u]+team[v]){
                        Maxteam[v]=Maxteam[u]+team[v];
                        pre[v]=u;
                    }
                }
            }
        }
    }
}

int main(){
    cin>>n>>m>>st>>ed;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j){
                map[i][j]=0;
            }else{
                map[i][j]=inf;
            }
        }
    }

    
    for(int i=0;i<n;i++){
        cin>>team[i];
    }
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        map[a][b]=map[b][a]=c;
    }
    dijkstra(st);
    cout<<roadnum[ed]<<" "<<Maxteam[ed]<<endl;
    printPath(ed);
}