最短路

﹏ヽ暗。殇╰゛Y 2021-11-18 00:30 255阅读 0赞

Floyed

[http://codevs.cn/problem/1077/][http_codevs.cn_problem_1077]

#include<cstdio>
    const int N=105;
    typedef long long ll; 
    ll dis[N][N];
    int main(){
        int n,q;
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j) scanf("%lld",&dis[i][j]);
        for(int k=1;k<=n;++k)
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j)
                    if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j];
        scanf("%d",&q);
        for(int i=1;i<=q;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            printf("%lld\n",dis[u][v]);
        }
        return 0;
    }

利用floyed求最小环

[http://acm.hdu.edu.cn/showproblem.php?pid=1599][http_acm.hdu.edu.cn_showproblem.php_pid_1599]

无向图

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int N=105,inf=1061109567;
    int dis[N][N],lb[N][N];
    int main(){
        int n,m,u,v,w;
        while(scanf("%d%d",&n,&m)!=EOF){
            int ans=inf;
            memset(dis,0x3f,sizeof(dis));
            memset(lb,0x3f,sizeof(lb));
            while(m--){
                scanf("%d%d%d",&u,&v,&w);
                lb[u][v]=lb[v][u]=dis[u][v]=dis[v][u]=min(lb[u][v],w);
            }
            for(int k=1;k<=n;++k){
                for(int i=1;i<k;++i)
                    if(lb[i][k]<inf)
                        for(int j=i+1;j<k;++j)
                            if(lb[j][k]<inf) ans=min(ans,lb[i][k]+lb[k][j]+dis[i][j]);
                for(int i=1;i<=n;++i)
                    for(int j=1;j<=n;++j)
                        if(lb[i][k]>0) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);     
            }
            if(ans==inf) printf("It's impossible.\n");
            else printf("%d\n",ans);
        }
        return 0;
    }

lg4779

[https://www.luogu.org/problemnew/show/P4779][https_www.luogu.org_problemnew_show_P4779]

dijkstra

#include<cstdio>
    #include<queue>
    #include<cstring> 
    using namespace std;
    const int N=1e5+5;
    struct E{
        int v,n,q;
    }e[N*5];
    int fir[N],s,dis[N],ss;
    bool vis[N];
    struct F{
        int v,q;
        bool operator<(const F &a)const{
            return q>a.q;
        } 
    }st;
    priority_queue<F>dl;
    void add(int u,int v,int q){
        e[++s].v=v;
        e[s].q=q;
        e[s].n=fir[u];
        fir[u]=s;
    }
    int main(){
        int n,m,u,v,q;
        scanf("%d%d%d",&n,&m,&st.v);
        while(m--){
            scanf("%d%d%d",&u,&v,&q);
            add(u,v,q);
        }
        dl.push(st);
        for(int i=1;i<=n;++i) dis[i]=2147483647;
        dis[st.v]=0;
        while(!dl.empty()){
            F t=dl.top();dl.pop();
            if(vis[t.v]) continue;
            vis[t.v]=1;++ss;
            for(int i=fir[t.v];i;i=e[i].n)
                if(t.q+e[i].q<dis[e[i].v]){
                    dis[e[i].v]=e[i].q+t.q;
                    if(!vis[e[i].v]) dl.push((F){e[i].v,dis[e[i].v]});
                }
        }
        for(int i=1;i<=n;++i)
            printf("%d ",dis[i]);
        return 0;
    }

lg3371

[https://www.luogu.org/problemnew/show/P3371][https_www.luogu.org_problemnew_show_P3371]

spfa

#include<cstdio>
    #include<queue>
    using namespace std;
    const int N=1e4+5,M=5e5+5;
    struct E{
        int v,q,n;
    }e[M];
    int fir[N],s,dis[N];
    queue<int>dl;
    bool vis[N];
    void add(int u,int v,int q){
        e[++s].v=v;
        e[s].q=q;
        e[s].n=fir[u];
        fir[u]=s;
    }
    int main(){
        int n,m,st,u,v,q;
        scanf("%d%d%d",&n,&m,&st);
        while(m--){
            scanf("%d%d%d",&u,&v,&q);
            add(u,v,q);
        }
        dl.push(st);
        vis[st]=1;
        for(int i=1;i<=n;++i) dis[i]=2147483647;
        dis[st]=0;
        while(!dl.empty()){
            u=dl.front();dl.pop();
            for(int i=fir[u];i;i=e[i].n)
                if(dis[u]+e[i].q<dis[e[i].v]){
                    dis[e[i].v]=dis[u]+e[i].q;
                    if(!vis[e[i].v]){
                        vis[e[i].v]=1;
                        dl.push(e[i].v);
                    }
                }
            vis[u]=0;
        }
        for(int i=1;i<=n;++i) printf("%d ",dis[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/bzmd/p/11119054.html

[http_codevs.cn_problem_1077]: http://codevs.cn/problem/1077/
[http_acm.hdu.edu.cn_showproblem.php_pid_1599]: http://acm.hdu.edu.cn/showproblem.php?pid=1599
[https_www.luogu.org_problemnew_show_P4779]: https://www.luogu.org/problemnew/show/P4779
[https_www.luogu.org_problemnew_show_P3371]: https://www.luogu.org/problemnew/show/P3371