SPFA ----模板 O(kE) (k一般不超过2)
2024-08-29 11:14:52
原理:若一个点入队的次数超过顶点数V,则存在负环;
#include "bits/stdc++.h" using namespace std;
const int maxN = ;
struct Edge
{
int to , next , w ;
} e[ maxN ]; int n,m,cnt,p[ maxN ],Dis[ maxN ];
int In[maxN ];
bool visited[ maxN ]; void Add_Edge ( const int x , const int y , const int z )
{
e[ ++cnt ] . to = y ;
e[ cnt ] . next = p[ x ];
e[ cnt ] . w = z ;
p[ x ] = cnt ;
return ;
} bool Spfa(const int S)
{
int i,t,temp;
queue<int> Q;
memset ( visited , , sizeof ( visited ) ) ;
memset ( Dis , 0x3f , sizeof ( Dis ) ) ;
memset ( In , , sizeof ( In ) ) ; Q.push ( S ) ;
visited [ S ] = true ;
Dis [ S ] = ; while( !Q.empty ( ) )
{
t = Q.front ( ) ;Q.pop ( ) ;visited [ t ] = false ;
for( i=p[t] ; i ; i = e[ i ].next )
{
temp = e[ i ].to ;
if( Dis[ temp ] > Dis[ t ] + e[ i ].w )
{
Dis[ temp ] =Dis[ t ] + e[ i ].w ;
if( !visited[ temp ] )
{
Q.push(temp);
visited[temp]=true;
if(++In[temp]>n)return false;
}
}
}
}
return true;
} int main ( )
{
int S , T ; scanf ( "%d%d%d%d" , &n , &m , &S , &T ) ;
for(int i= ; i<=m ; ++i )
{
int x , y , _ ;
scanf ( "%d%d%d" , &x , &y , &_ ) ;
Add_Edge ( x , y , _ ) ;
} if ( !Spfa ( S ) ) printf ( "FAIL!\n" ) ;
else printf ( "%d\n" , Dis[ T ] ) ; return ;
}
最新文章
- 关于一个parent(),siblings()的小问题
- 原创 | 《地狱边境》登顶50国iOS下载榜,恐怖游戏或是独立开发者突破口(转)
- 第32讲 UI组件之 时间日期控件DatePicker和TimePicker
- sql2008R2sp1局域网镜像环境实操(无见证服务器)
- Codeforces Round #258 (Div. 2) 小结
- Python爬虫入门教程 38-100 教育部高校名单数据爬虫 scrapy
- python从开始到放弃的途中一直很菜的day13
- 从零打卡leetcode之day 4--无重复最长字符串
- Jmeter中使用外部的java文件
- Ubuntu 下 Python自由切换
- CentOS之Vim
- HDU 2029 算菜价
- scala工程导入报错:scalatest_2.10-1.9.1.jar is cross-compiled with an incompatible version of Scala (2.10).
- Spring学习笔记之各个包的作用
- [ACM_数据结构] 线段树模板
- C# 非模式窗体show()和模式窗体showdialog()的区别
- 001-Spring的设计理念和整体架构
- maven 整合 ssm 异常分析
- springboot数据库操作及事物管理操作例子
- 使用pipework将Docker容器配置到本地网络环境中
热门文章
- Python中的绝对路径和相对路径
- python之元组,列表和字典的区别
- Python +selenium之集成测试报告与unittest单元测试
- UVA 11093 Just Finish it up 环形跑道 (贪心)
- [论文理解] CornerNet: Detecting Objects as Paired Keypoints
- PAT (Basic Level) Practise (中文)- 1007. 素数对猜想 (20)
- JQuery EasyUI学习记录(五)
- nodejs个人博客系统
- lua调用java过程
- (71)Received empty response from Zabbix Agent问题解决