文档章节

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;
}


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 95
博文 49
码字总数 34362
作品 0
海淀
程序员
私信 提问
1.1.1最短路(Floyd、Dijstra、BellmanFord)

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

fire_to_cheat_
03/04
0
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
04/16
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......

语海与冰
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
02/01
0
0
[BZOJ2709] [Violet 1]迷宫花园

http://www.lydsy.com/JudgeOnline/problem.php?id=2709 这题是权限题,版权问题不放题意,我来简要的说一下: 给出一个迷宫,有起始点终点,可以上下左右走,移动的耗时是1,可以改变上下走...

CABI_ZGX
02/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

day152-2018-11-19-英语流利阅读

“超级食物”竟然是营销噱头? Daniel 2018-11-19 1.今日导读 近几年来,超级食物 superfoods 开始逐渐走红。不难发现,越来越多的轻食餐厅也在不断推出以超级食物为主打食材的健康料理,像是...

飞鱼说编程
16分钟前
0
0
SpringBoot源码:启动过程分析(二)

接着上篇继续分析 SpringBoot 的启动过程。 SpringBoot的版本为:2.1.0 release,最新版本。 一.时序图 一样的,我们先把时序图贴上来,方便理解: 二.源码分析 回顾一下,前面我们分析到了下...

Jacktanger
昨天
0
0
Apache防盗链配置,Directory访问控制,FilesMatch进行访问控制

防盗链配置 通过限制referer来实现防盗链的功能 配置前,使用curl -e 指定referer [root@test-a test-webroot]# curl -e "http://www.test.com/1.html" -x127.0.0.1:80 "www.test.com/1.jpg......

野雪球
昨天
2
0
RxJava threading

因为Rx针对异步系统设计,并且Rx也自然支持多线程,所以新的Rx开发人员有时会假设Rx默认是多线程的。在其他任何事情之前,重要的是澄清Rx默认是单线程的。 除非另有说明,否则每次调用onNex...

woshixin
昨天
0
0
Python的安装及文件类型、变量

一、为什么学习python 服务于大数据、人工智能、自动化运维。 简单易学 代码简洁 薪资高 近几年越来越火 二、Python的安装 linux 系统默认安装, CentOS7 默认安装了python2.7 安装ipython y...

枫叶云
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部