1 条题解

  • 0
    @ 2023-2-1 16:33:23

    Dijkstra 算法 *2

    正常存一遍图,再把有向边的方向反过来存进另一个图,然后分别找一下路径就行了。

    (MAXN开1e4+5就会爆内存了,可以不用反着存一遍图,在搜的时候方向反着搜一遍也行)

    // Created by FlyingPig278 on 2/1/23.
    #include<bits/stdc++.h>
    using namespace std;
    
    #define lld long long
    
    const int MAXN=1e3+5;
    const int INF=0x7f7f7f7f;
    
    lld read() {
        lld ans = 0, f = 1;
        char ch = getchar();
        while (!isdigit(ch)) f *= (ch == '-')? -1 : 1, ch = getchar();
        while (isdigit(ch)) ans = ((ans << 1) + (ans << 3) + (ch ^ 48)), ch = getchar();
        return ans * f;
    }
    
    int g[MAXN][MAXN],g2[MAXN][MAXN],dis[MAXN],dis2[MAXN];
    bool flag[MAXN],flag2[MAXN];
    
    int main(){
        memset(g,0x7f,sizeof(g));
        memset(g2,0x7f,sizeof(g2));
        int n=read(),m=read(),s=read();
        for(int i=1;i<=n;i++){
            g[i][i]=g2[i][i]=0;
        }
        for(int i=1;i<=m;i++){
            int u=read(),v=read(),w=read();
            g[u][v]=min(g[u][v],w);
            g2[v][u]=min(g2[v][u],w);
        }
        for(int i=1;i<=n;i++){
            dis[i]=g[s][i];
            dis2[i]=g2[s][i];
        }
        flag[s]=1;
        flag2[s]=1;
        for(int i=1;i<=n;i++){
            int mins=INF;
            int mins2=INF;
            int u;
            int u2;
            for(int j=1;j<=n;j++){
                if(!flag[j]&&dis[j]<mins){
                    mins=dis[j];
                    u=j;
                }
                if(!flag2[j]&&dis2[j]<mins2){
                    mins2=dis2[j];
                    u2=j;
                }
            }
            flag[u]=1;
            flag2[u2]=1;
            for(int j=1;j<=n;j++){
                if(g[u][j]!=INF){
                    dis[j]=min(dis[j],dis[u]+g[u][j]);
                }
                if(g2[u2][j]!=INF){
                    dis2[j]=min(dis2[j],dis2[u2]+g2[u2][j]);
                }
            }
        }
        int ans=-1;
        for(int i=1;i<=n;i++){
            if(dis[i]!=INF&&dis2[i]!=INF) ans=max(ans,dis[i]+dis2[i]);
        }
        cout<<ans;
        return 0;
    }
    
    • 1

    信息

    ID
    1337
    时间
    1000ms
    内存
    512MiB
    难度
    8
    标签
    递交数
    124
    已通过
    18
    上传者