首页 > 其他 > 详细

bellman-ford模板

时间:2018-02-14 18:33:11      阅读:27      评论:0      收藏:0      [点我收藏+]

标签:class   con   max   brush   emp   pop   empty   vector   als   

题目大意:

最短路;

基本思路:

松弛;

代码如下:

struct Edge{
    int to,w;
    bool operator<(const Edge& rhs)const{
        return w>rhs.w;
    }
}edge[maxn];
vector<int>gra[maxn];
int dis[maxn],cnt[maxn];
bool vis[maxn];
bool bellman_ford(int s){
    queue<int>q;q.push(s);
    memset(vis,false,sizeof(vis));vis[s]=true;
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<n;i++) dis[i]=inf; dis[s]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=false;
        int sz=gra[u].size();
        for(int i=0;i<sz;i++){
            Edge& e=edge[gra[u][i]];
            if(dis[e.to]>dis[u]+e.w){
                dis[e.to]=dis[u]+e.w;
                if(!vis[e.to]){
                    q.push(e.to);
                    vis[e.to]=true;
                    cnt[e.to]++;
                    if(cnt[e.to]>n){
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

  

bellman-ford模板

标签:class   con   max   brush   emp   pop   empty   vector   als   

原文:https://www.cnblogs.com/imzscilovecode/p/8448640.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号