最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 最短路之SPFA模板

    1:邻接矩阵版本SPFA//如果要判断负环的话加1个记录入队的数组就行,当入队次数大于n的时候出现负环

    int d[MAXN],vis[MAXN],w[MAXN][MAXN];
    int n;
    void SPFA(int s)
    {
    fill(d,d+n,INF);
    d[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
    int u=q.front();
    q.pop();
    for(int v=0; v<n; v++)
    {
    if(d[v]>d[u]+w[u][v])
    {
    d[v]=d[u]+w[u][v];
    q.push(v);

    }
    }
    }
    }

    2:伪邻接表版SPFA

    const int inf = 0x3f3f3f3f;
    int v[M],w[M],next[M],head[N],d[N],e;//head初始化为⑴,摹拟邻接表
    void addedge(int a,int b,int x)//主要如果是无向图的话,每条边要履行两次这个,a,b反过来就行
    {
    v[e]=b;
    w[e]=x;
    next[e]=head[a];
    head[a]=e++;
    }

    void SPFA(int s)
    {
    queue<int> q;
    d[s]=0;
    q.push(s);
    while(!q.empty())
    {
    int u = q.front();
    q.pop();
    for(int i=head[u]; i!=⑴; i=next[i])
    {
    if(d[v[i]]>d[u]+w[i])
    {
    d[v[i]]=d[u]+w[i];
    q.push(v[i]);
    }
    }
    }
    }

    for(int i=0; i<m; i++)//输入1条带权值的无向边
    {
    cin>>a>>b>>x;
    addedge(a,b,x);
    addedge(b,a,x);
    }

    3:邻接表版

    struct Edge
    {
    int to,w,next;
    }E[maxn];

    void init()
    {
    memset(head,⑴,sizeof(head));
    fill(d,d+n,INF);
    size = 0;
    }

    void addedge(int u,int v,int x)
    {
    E[size].to = v;
    E[size].w = x;
    E[size].next = head[u];
    head[u] = size++;
    }

    void SPFA(int s)
    {
    queue<int> q;
    d[s]=0;
    q.push(s);
    while(!q.empty())
    {
    int u = q.front();
    q.pop();
    for(int i=head[u]; i!=⑴; i=E[i].next)
    {
    if(d[E[i].to] > d[u] + E[i].w)
    {
    d[E[i].to] = d[u]+E[i].w;
    q.push(E[i].to);
    }
    }
    }
    }

    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » 最短路之SPFA模板

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级