文档章节

SPFA做最短路

侯禹
 侯禹
发布于 2013/10/02 16:12
字数 275
阅读 183
收藏 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
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
LightOJ - 1074 Extended Traffic 【spfa判负环 + dfs】

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

Anxdada
02/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

分布式锁的那点事

在多线程并发的情况下,要保证一个代码块在同一时间只能由一个线程访问,可以用锁来保证,比如java的synchronized语法以及ReentrantLock类等等。这样子可以保证JVM进程内的多个线程同步执行。...

无语年华
20分钟前
2
0
apahce启用http2

需要前置条件传送门 其实前置做完了,h2是很简单的事 1.apache启用http2_module 2.打开apche的配置文件,写上 Protocols h2 http/1.1 3.重启apache,打开浏览器看看吧...

gcudwork
35分钟前
1
0
redis-string

set key value 设置值 set命令有以下选项: ex senconds :为健设置秒级过期时间 px millisencondes :为健设置毫秒级过期时间 nx :健不存在时候,可以设置成功,用于添加 xx : 与nx相反,不...

拐美人
41分钟前
2
0
正弦 余弦 角度 用于画时钟

<html> <head> <title>时钟</title> </head> <style> #canvas{ background: #1977ca } </style>......

一箭落旄头
58分钟前
4
0
驰狼课堂

http://www.chilangedu.com/

求是科技
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部