@zzzc18 2017-11-10T11:28:46.000000Z 字数 1218 阅读 1774

# DFS_SPFA

最短路

SPFA算法的优化及应用.pdf467.2kB

#include<queue>#include<cstdio>#include<cstring>#include<algorithm>#include<climits>using namespace std;typedef long long LL;const int MAXN = 10000+9;const int MAXM = 500000+9;int n,m;struct E{    int next,to;    LL val;}edge[MAXM];int head[MAXN],edge_num;int S;LL dis[MAXN];void addedge(int x,int y,LL v){    edge[++edge_num].next=head[x];    edge[edge_num].to=y;    edge[edge_num].val=v;    head[x]=edge_num;}void Build(){    scanf("%d%d%d",&n,&m,&S);    for(int i=1;i<=m;i++){        int a,b;        LL c;        scanf("%d%d%lld",&a,&b,&c);        addedge(a,b,c);    }    for(int i=1;i<=n;i++)        dis[i]=INT_MAX;    dis[S]=0;}bool SPFA_INIT(int x,int step,int lim){    if(step==lim)return true;    for(int i=head[x];i;i=edge[i].next){        if(dis[edge[i].to]>dis[x]+edge[i].val){            dis[edge[i].to]=dis[x]+edge[i].val;            SPFA_INIT(edge[i].to,step+1,lim);            return true;        }    }    return false;}void SPFA(int x,int step,int lim){    if(step==lim)        return;    for(int i=head[x];i;i=edge[i].next){        if(dis[edge[i].to]>dis[x]+edge[i].val){            dis[edge[i].to]=dis[x]+edge[i].val;            SPFA(edge[i].to,step+1,lim);        }    }}int main(){    Build();    for(int i=0;(1<<i-1)<=n;i++){        int depth=1<<i;        for(int j=1;j<=n;j++){            if(SPFA_INIT(j,0,depth)){                for(int k=1;k<=n;k++){                    SPFA(k,0,depth);                }            }        }    }    for(int i=1;i<=n;i++)        printf("%d ",dis[i]);    return 0;}

• 私有
• 公开
• 删除