最短路的三种写法

发布时间:2016-12-19 11:47:17编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"最短路的三种写法 ",主要涉及到最短路的三种写法 方面的内容,对于最短路的三种写法 感兴趣的同学可以参考一下。

SPFA

#include <iostream>#include <cstdio>#include <vector>#include <cstring>#include <queue>using namespace std;const int maxn=205;const int INF=1e9;int inq[maxn],d[maxn],n,m,s,t;struct node{    int v,w;    node(int _v,int _w):v(_v),w(_w){}};vector<node> E[maxn];void init(){    int i;    memset(inq,0,sizeof(inq));    for(i=0;i<maxn;++i) E[i].clear();    for(i=0;i<maxn;++i) d[i]=INF;}int main(){    while(~scanf("%d%d",&n,&m)){        init();        int i,u,v,w;        for(i=0;i<m;++i){            scanf("%d%d%d",&u,&v,&w);            E[u].push_back(node(v,w));            E[v].push_back(node(u,w));        }        scanf("%d%d",&s,&t);        queue<int> que;        que.push(s);d[s]=0;inq[s]=1;        while(!que.empty()){            int now=que.front();            que.pop();inq[now]=0;            for(i=0;i<E[now].size();++i){                node T=E[now][i];                int tv=T.v,tw=T.w;                if(d[tv]>d[now]+tw){                    d[tv]=d[now]+tw;                    if(inq[tv]) continue;                    que.push(tv);inq[tv]=1;                }            }        }        if(d[t]==INF)     printf("-1\n");        else             printf("%d\n",d[t]);    }    return 0;}

迪杰斯特拉

#include <iostream>#include <cstdio>#include <vector>#include <queue>#include <cstring>using namespace std;const int maxn=205;const int INF=1e9;//pay attentionint d[maxn],n,m,s,t;struct node{    int v,w;    node(int _v,int _w):v(_v),w(_w){}    bool operator < (const node&t) const{        return w>t.w;    }    //理解为数组排序后输出最后一个元素};vector<node> E[maxn];bool vis[maxn];void init(){    int i;    memset(vis,0,sizeof(vis));    for(i=0;i<maxn;++i) d[i]=INF;    for(i=0;i<maxn;++i) E[i].clear();}int main(){    while(~scanf("%d%d",&n,&m)){        init();        int i,u,v,w;        for(i=0;i<m;++i){            scanf("%d%d%d",&u,&v,&w);            E[u].push_back(node(v,w));            E[v].push_back(node(u,w));        }        scanf("%d%d",&s,&t);        d[s]=0;priority_queue<node> que;que.push(node(s,d[s]));        while(!que.empty()){            node now=que.top();            que.pop();vis[now.v]=true;            if(now.v==t) break;//显然已经求出到t的最短路            for(i=0;i<E[now.v].size();++i){                node T=E[now.v][i];                int tv=T.v,tw=T.w;                if(!vis[tv]&&d[tv]>d[now.v]+tw){                    d[tv]=d[now.v]+tw;                    que.push(node(tv,d[tv]));                }            }        }        if(d[t]==INF)     printf("-1\n");        else             printf("%d\n",d[t]);    }    return 0;}

floyd--dp算法。。dp[k][i][j]中间经过1~k,i,j的最短路,dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j])

后面都是k-1...因为。。k还没算出来呢。。怎么能依赖没有计算出的项呢。。

#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int maxn=205;const int INF=1e9;int d[maxn],n,m,s,t;int E[maxn][maxn];void init(){    int i,j;    for(i=0;i<maxn;++i){        for(j=0;j<maxn;++j){            E[i][j]=INF;            if(i==j) E[i][j]=0;        }    }}int main(){    //还是得先读一遍题    while(~scanf("%d%d",&n,&m)){        int i,j,k,u,v,w;        init();        for(i=0;i<m;++i){            scanf("%d%d%d",&u,&v,&w);            E[u][v]=min(E[u][v],w);            E[v][u]=min(E[u][v],w);            //有重边。。            //邻接矩阵一条边只能存一个权            //不能存复权        }        for(k=0;k<n;++k){            for(i=0;i<n;++i){                for(j=0;j<n;++j){                    if(E[i][j]>E[i][k]+E[k][j]){//先计算依赖项                        E[i][j]=E[i][k]+E[k][j];                    }                }            }        }        scanf("%d%d",&s,&t);        if(E[s][t]==INF)     printf("-1\n");        else                 printf("%d\n",E[s][t]);    }    return 0;}


上一篇:nginx配置杂记
下一篇:快来熟练使用 Mac 编程

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款