// spfa算法.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <cstdio>
//using namespace std;
struct node
{int x;
int value;
int next;
};
node e[60000];
int visited[1505],dis[1505],st[1505],queue[1000];
main()
{
int n,m,u,v,w,start,h,r,cur;
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=1500;i++)
{visited[i]=0;
dis[i]=-1;
st[i]=-1;
}
for( i=1;i<=m;i++)
{
scanf("%d%d%d\n",&u,&v,&w);
e[i].x=v;
e[i].value=w;
e[i].next=st[u];
st[u]=i;
}
start=1;
visited[start]=1;
dis[start]=0;
h=0;
r=1;
queue[r]=start;
while(h!=r)
{
h=(h+1)%1000;
cur=queue[h];
int tmp=st[cur];
visited[cur]=0;
while(tmp!=-1)
{
if (dis[e[tmp].x]<dis[cur]+e[tmp].value)
{
dis[e[tmp].x]=dis[cur]+e[tmp].value;
if(visited[e[tmp].x]==0)
{
visited[e[tmp].x]=1;
r=(r+1)%1000;
queue[r]=e[tmp].x;
}
}
tmp=e[tmp].next;
}
}
printf("%d\n",dis[n]);
}
return 0;
}
spfa.zip_SPFA 无向图
版权申诉
132 浏览量
2022-09-24
05:11:13
上传
评论
收藏 727B ZIP 举报
小贝德罗
- 粉丝: 68
- 资源: 1万+
最新资源
- 二叉树7-1-1.cpp
- android 9.0 原生模拟器 签名文件
- 技术面试最后反问面试官的话 校招面试非技术问题有哪些 非技术问题如何回答.png
- NB-IOT-BC26全网通模块Altium+ CADENCE +PADS三种格式(原理图SCH+PCB封装库)文件.zip
- 基于微信小程序开发的校园失物招领系统源码毕业设计(优质项目源码).zip
- 词向量是一种将自然语言中的单词转换为数值向量的技术,它能够捕捉词义和上下文信息
- nmap与masscan的简单使用
- MyBatis动态SQL.pdf
- 基于stm32单片机protues仿真的温湿度控制系统设计(仿真图、源代码)
- 词向量:自然语言处理的基石
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈