文档章节

SPFA做最短路

侯禹
 侯禹
发布于 2013/10/02 16:12
字数 275
阅读 181
收藏 3
点赞 0
评论 0
#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;
}


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 94
博文 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 ⋅ 04/16 ⋅ 0

1.1.1最短路(Floyd、Dijstra、BellmanFord)

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

fire_to_cheat_ ⋅ 03/04 ⋅ 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

[BZOJ2709] [Violet 1]迷宫花园

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

CABI_ZGX ⋅ 02/03 ⋅ 0

LightOJ - 1074 Extended Traffic 【spfa判负环 + dfs】

传送门 题意:给定(n, m)有向图, 每个点有点权, u->v的代价是(a[v]-a[u])^3, 给出q个询问, 问从1出发到询问的该点的最小代价, 如果代价<3或者不能到达该点输出’?’. 思路: 很明显这幅图是可...

Anxdada ⋅ 02/13 ⋅ 0

POJ ~ 3159 ~ Candies (Dijkstra + 优先队列 + 链式前向星 or 栈式SPFA)(差分约束)

推荐一片入门博客:夜深人静写算法(四) - 差分约束 个人感觉很有用的地方,暂存一下,备查: 4、最大值 => 最小值 然后,我们将问题进行一个简单的转化,将原先的"<="变成">=",转化后的不...

ZscDst ⋅ 01/31 ⋅ 0

最短路径算法

单源最短路径问题 问题描述:给你一个顶点做源点,你想要知道,如何从源点到达其他所有点的最短路径。 OK,这个问题看起来没什么用。我们一般想知道的是A点到B点的最短路径,这个单源最短路径...

Hosee ⋅ 2016/01/14 ⋅ 0

PAT(Advanced Level) 1003. Emergency(25) 最短路 + DFS

题目链接 Emergency Time limit:1 seconds Memory limit:256 megabytes Problem Description IAs an emergency rescue team leader of a city, you are given a special map of your country......

xp731574722 ⋅ 03/07 ⋅ 0

[poj2449]Remmarguts' Date(k短路学习笔记)

题目大意就是给出一个图,然后一个起点一个终点,求这两点间的第K短路。 一般做法:SPFA+A k短路的话,我们可以马上想到一个宽搜的做法,从st开始宽搜,当第k次搜索到ed时,所得到的长度即所...

CABI_ZGX ⋅ 2017/12/30 ⋅ 0

OI一些奇怪的优化手段和常用技巧

经典的O3优化(一般写在开头) #pragma GCC optimize("O3") pragma G++ optimize("O3") G++手动扩大栈(写在main的开始) int size = 256 << 20; // 256MB char p = (char)malloc(size) + s......

JacaJava ⋅ 2017/10/25 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

如何优雅的编程——C语言界面的一点小建议

我们鼓励在编程时应有清晰的哲学思维,而不是给予硬性规则。我并不希望你们能认可所有的东西,因为它们只是观点,观点会随着时间的变化而变化。可是,如果不是直到现在把它们写在纸上,长久以...

柳猫 ⋅ 37分钟前 ⋅ 0

从零手写 IOC容器

概述 IOC (Inversion of Control) 控制反转。熟悉Spring的应该都知道。那么具体是怎么实现的呢?下面我们通过一个例子说明。 1. Component注解定义 package cn.com.qunar.annotation;impo...

轨迹_ ⋅ 38分钟前 ⋅ 0

系统健康检查利器-Spring Boot-Actuator

前言 实例由于出现故障、部署或自动缩放的情况,会进行持续启动、重新启动或停止操作。它可能导致它们暂时或永久不可用。为避免问题,您的负载均衡器应该从路由中跳过不健康的实例,因为它们...

harries ⋅ 39分钟前 ⋅ 0

手把手教你搭建vue-cli脚手架-详细步骤图文解析[vue入门]

写在前面: 使用 vue-cli 可以快速创建 vue 项目,vue-cli很好用,但是在最初搭建环境安装vue-cli及相关内容的时候,对一些人来说是很头疼的一件事情,本人在搭建vue-cli的项目环境的时候也是...

韦姣敏 ⋅ 50分钟前 ⋅ 0

12c rman中输入sql命令

12c之前版本,要在rman中执行sql语句,必须使用sql "alter system switch logfile"; 而在12c版本中,可以支持大量的sql语句了: 比如: C:\Users\zhengquan>rman target / 恢复管理器: Release 1...

tututu_jiang ⋅ 今天 ⋅ 0

Nginx的https配置记录以及http强制跳转到https的方法梳理

Nginx的https配置记录以及http强制跳转到https的方法梳理 一、Nginx安装(略) 安装的时候需要注意加上 --with-httpsslmodule,因为httpsslmodule不属于Nginx的基本模块。 Nginx安装方法: ...

Yomut ⋅ 今天 ⋅ 0

SpringCloud Feign 传递复杂参数对象需要注意的地方

1.传递复杂参数对象需要用Post,另外需要注意,Feign不支持使用GetMapping 和PostMapping @RequestMapping(value="user/save",method=RequestMethod.POST) 2.在传递的过程中,复杂对象使用...

@林文龙 ⋅ 今天 ⋅ 0

如何显示 word 左侧目录大纲

打开word说明文档,如下图,我们发现左侧根本就没有目录,给我们带来很大的阅读障碍 2 在word文档的头部菜单栏中,切换到”视图“选项卡 3 然后勾选“导航窗格”选项 4 我们会惊奇的发现左侧...

二营长意大利炮 ⋅ 今天 ⋅ 0

智能合约编程语言Solidity之线上开发工具

工具地址:https://ethereum.github.io/browser-solidity/ 实例实验: 1.创建hello.sol文件 2.调试输出结果

硅谷课堂 ⋅ 今天 ⋅ 0

ffmpeg 视频格式转换

转 Mp4 格式 #> ffmpeg -i input.avi -c:v libx264 output.mp4#> ffmpeg -i input.avi -c:v libx264 -strict -2 output.mp4#> ffmpeg -i input.avi -c:v libx264 -strict -2 -s 1......

Contac ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部