文档章节

SPFA做最短路

侯禹
 侯禹
发布于 2013/10/02 16:12
字数 275
阅读 185
收藏 3
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define Inf 0x7fffffff
#define MaxV 10000
#define MaxE 10000
using namespace std;
int N,M;      //边数
struct Edge
{
    int to,next,w;
}edge[MaxE];
int size,head[MaxV];
void InsertEdge(int from,int to,int w)
{
    edge[size].to=to;
    edge[size].w = w;
    edge[size].next=head[from];
    head[from]=size++;
}
int dist[MaxV];
int  cot[MaxV];
bool vst[MaxV];
int path[MaxV];
bool spfa(int s)
{
    int i;
    int from,to;
    queue<int> que;
    memset(vst,0,sizeof(vst));
    memset(cot,0,sizeof(cot));
    //memset(dist,Inf,sizeof(dist));
    for(i=0;i<=N;i++)
        path[i]=i,dist[i]=Inf;
    path[s]=0,dist[s]=0;
    que.push(s),vst[s]=1;
    while(!que.empty())
    {
        from=que.front();
        que.pop(),vst[from]=0,cot[from]++;
        if(cot[from]>=N)    return 0;
        for(i=head[from];i+1;i=edge[i].next)
        //当head=-1的时候,停止,证明其没有
        {
            to=edge[i].to;
            if(dist[to]>dist[from]+edge[i].w)
            {
                dist[to]=dist[from]+edge[i].w;
                if(!vst[to])
                    que.push(to),vst[to]=1;
            }
        }
    }
    for(i=1;i<=N;i++)
    printf("dist[%d]   =  %d\n",i,dist[i]);
    return 1;
}
void init()
{
    int from,to,w;
    size=0;
    memset(head,-1,sizeof(head));
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++)
    {
        scanf("%d%d%d",&from,&to,&w);
        InsertEdge(from,to,w);
    }
}
int main()
{
    freopen("in.txt","r",stdin);
    init();
    if(!spfa(1))    printf("存在负环回路\n");
    else printf("存在最短路径\n");
    return 0;
}


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 96
博文 49
码字总数 34362
作品 0
海淀
程序员
私信 提问
HDU 6166-Senior Pan(详解!最短路+二进制优化划分集合)

Senior Pan fails in his discrete math exam again. So he asks Master ZKC to give him graph theory problems everyday. The task is simple : ZKC will give Pan a directed graph every......

akatsuki__itachi
2018/04/16
0
0
1.1.1最短路(Floyd、Dijstra、BellmanFord)

转载自hr_whisper大佬的博客 一、Dijkstra 比较详细的迪杰斯特拉算法讲解传送门 Dijkstra单源最短路算法,即计算从起点出发到每个点的最短路。所以Dijkstra常常作为其他算法的预处理。 使用邻...

fire_to_cheat_
2018/03/04
0
0
动态删边SPFA: [HNOI2014]道路堵塞

[HNOI2014]道路堵塞 题目描述 A国有N座城市,依次标为1到N。同时,在这N座城市间有M条单向道路,每条道路的长度是一个正整数。现在,A国交通部指定了一条从城市1到城市N的路径,并且保证这条...

Rockyyh
2018/12/03
0
0
PAT 1003 Emergency(SPFA+dfs回溯记录最短路径条数)

版权声明:转载请告知博主并要注明出处嗷~ https://blog.csdn.net/AkatsukiItachi/article/details/83176838 PAT1003 1003 Emergency (25 分) As an emergency rescue team leader of a ci......

语海与冰
2018/10/19
0
0
LightOJ ~ 1074 ~ Extended Traffic (SPFA + DFS判点是否在负环中)

题意:T组测试数据,N个点,编号1~N,然后输入这N个点的一个数值。然后又M条边A~B的权值为(B点数值 - A点数值)^3,然后又Q次询问,问1点到X点的最短路为多少?如果①最短路小于3或②不能到...

ZscDst
2018/02/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周五乱弹 —— 姑娘馋的口水都留下来了。

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @且无需多言 :分享Fall Out Boy的单曲《Disloyal Order Of Water Buffaloes》 《Disloyal Order Of Water Buffaloes》- Fall Out Boy 手机党...

小小编辑
今天
74
7
vue 对对象的属性进行修改时,不能渲染页面 vue.$set()

我在vue里的方法里给一个对象添加某个属性时,我console.log出来的是已经更改的object ,但是页面始终没有变化 原因如下: **受现代 JavaScript 的限制 (而且 Object.observe 也已经被废弃),...

Js_Mei
今天
2
0
开始看《Java学习笔记》

虽然书买了很久,但一直没看。这其中也写过一些Java程序,但都是基于IDE的帮助和对C#的理解来写的,感觉不踏实。 林信良的书写得蛮好的,能够帮助打好基础,看得出作者是比较用心的。 第1章概...

max佩恩
昨天
12
0
Redux 三大原则

1.单一数据源 在传统的MVC架构中,我们可以根据需要创建无数个Model,而Model之间可以互相监听、触发事件甚至循环或嵌套触发事件,这些在Redux中都是不被允许的。 因为在Redux的思想里,一个...

wenxingjun
昨天
9
0
跟我学Spring Cloud(Finchley版)-12-微服务容错三板斧

至此,我们已实现服务发现、负载均衡,同时,使用Feign也实现了良好的远程调用——我们的代码是可读、可维护的。理论上,我们现在已经能构建一个不错的分布式应用了,但微服务之间是通过网络...

周立_ITMuch
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部