L2-001 紧急救援

unsolved PTA 最短路 C++ 所有文稿

紧急救援

关键词：unsolved，dijkstra，邻接表，两次松弛

用pre数组记录前一个城市，第二次对长度相同的路线进行城市救援军数量的松弛，path数组目前看来可有可无，直接用dis[s]替代即可。

案例只通过了一半，对照着网上参考的算法debug了老半天，除了顺序之外没有发现任何区别。

我的版本（为了和参考代码尽可能相同，改了很多）

/*16:30-17:03*/
/*18:30*/
#include <iostream>
#include <stack>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int maxn=510,MAX=0x3f3f3f;
int n,m,s,d;
int dis[maxn][maxn],a[maxn],vis[maxn],num[maxn];
int path[maxn];//最短路值
int maxx[maxn];//最短路径最大的权值和
int pre[maxn];
int main(){
    cin>>n>>m>>s>>d;
    memset(dis,MAX,sizeof(dis));
    memset(path,0,sizeof(path));
    memset(maxx,0,sizeof(maxx));
    memset(pre,0,sizeof(pre));
    memset(num,0,sizeof(num));
    memset(a,0,sizeof(a));
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++) {cin>>a[i];num[i]=1;}
    /*for(int i=0;i<maxn;i++){
    for(int j=0;j<maxn;j++){
    if (i==j) dis[i][j]=0;
    else dis[i][j]=MAX;
    }
    }*/
    for(int i=0;i<m;i++){
        int a,b,len;
        cin>>a>>b>>len;
        dis[a][b]=min(dis[a][b],len);//a到b的路
        dis[b][a]=min(dis[a][b],len);
    }
    for(int i=0;i<n;i++){
        if(i==s){
            path[i]=0;
            maxx[i]=a[i];
        }
        else{
            path[i]=dis[s][i];
            maxx[i]=a[s]+a[i];//划重点 这是干嘛？
        }
        if(i!=s&&dis[s][i]!=MAX)//与起点直接连接
            pre[i]=s;
        else pre[i]=-1;
    }
    vis[s]=1;
    for(int z=0;z<n;z++){
        int min=MAX,min_n;
        for(int i=0;i<n;i++){
            if (dis[s][i]<min&&!vis[i]){
                min=path[i];
                min_n=i;
            }
        }
        if(min==MAX){
            break;    //不连通
        }
        vis[min_n]=1;
        //printf("insert min_n=%d\nset size=%d\n",min_n,found.size());
        /*
        for(int i=0;i<n;i++){
        if (!vis[i]){
        if (dis[s][i]>dis[min_n][i]+dis[s][min_n]){
        dis[s][i]=dis[min_n][i]+dis[s][min_n];
        maxx[i]=maxx[min_n]+a[i];
        pre[i]=min_n;
        num[i]=num[min_n];
        }
        else if(dis[s][i]==dis[min_n][i]+dis[s][min_n]){
        num[i]+=num[min_n];
        if (maxx[i]<maxx[min_n]+a[min_n]){
        maxx[i]=maxx[min_n]+a[i];
        pre[i]=min_n;
        }
        }
        }
        }*/
        int k=min_n;
        for(int j=0;j<n;j++){
            if(!vis[j]){
                if(path[j]>path[min_n]+dis[k][j]){
                    path[j]=path[k]+dis[k][j];
                    maxx[j]=maxx[k]+a[j];
                    pre[j]=k;
                    num[j]=num[k];
                }
                else if(path[j]==path[k]+dis[k][j]){
                    num[j]=num[j]+num[k];
                    if(maxx[j]<maxx[k]+a[j]){
                        maxx[j]=maxx[k]+a[j];
                        pre[j]=k;
                    }
                    //maxx[j]=max(maxx[j],maxx[k]+a[j]);
                }
            }
        }
    }
    cout<<num[d]<<" "<<maxx[d]<<endl;
    int sp=0;
    stack<int> st;
    for(int i=d;i!=-1;i=pre[i]) {st.push(i);}
    while(!st.empty()){
        if (sp++) cout<<" ";
        cout<<st.top();
        st.pop();
    }
    cout<<endl;
    system("pause");
    return 0;
}

参考算法

2019.3.16