「单源最短路径」Bellman-Ford

这本来是个非常和谐的单源最短路径模板
但是会被连洛谷P3371的数据卡掉
果然,Bellman-Ford还是一如既往的慢……

#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=10000+5;
const int maxm=500000+5;
int n,m,b;
int dis[maxn],u[maxm],v[maxm],w[maxm];
void initialize_single_source(int s){
    for(int i=1;i<=n;i++){
        dis[i]=INF;
    }
    dis[s]=0;
}
void bellman_ford(int s){
    initialize_single_source(s);
    for(int k=1;k<=n-1;k++){
        for(int i=1;i<=m;i++){
            if(dis[v[i]]>dis[u[i]]+w[i]){
                dis[v[i]]=dis[u[i]]+w[i];
            }
        }
    }
    for(int k=1;k<=n-1;k++){
        for(int i=1;i<=m;i++){
            if(dis[v[i]]>dis[u[i]]+w[i]){
                dis[v[i]]=0x7fffffff;
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&amp;n,&amp;m,&amp;b);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&amp;u[i],&amp;v[i],&amp;w[i]);
    }
    bellman_ford(b);
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    printf("\n");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注