原理:若一个点入队的次数超过顶点数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 ;
}

最新文章

  1. 关于一个parent(),siblings()的小问题
  2. 原创 | 《地狱边境》登顶50国iOS下载榜,恐怖游戏或是独立开发者突破口(转)
  3. 第32讲 UI组件之 时间日期控件DatePicker和TimePicker
  4. sql2008R2sp1局域网镜像环境实操(无见证服务器)
  5. Codeforces Round #258 (Div. 2) 小结
  6. Python爬虫入门教程 38-100 教育部高校名单数据爬虫 scrapy
  7. python从开始到放弃的途中一直很菜的day13
  8. 从零打卡leetcode之day 4--无重复最长字符串
  9. Jmeter中使用外部的java文件
  10. Ubuntu 下 Python自由切换
  11. CentOS之Vim
  12. HDU 2029 算菜价
  13. scala工程导入报错:scalatest_2.10-1.9.1.jar is cross-compiled with an incompatible version of Scala (2.10).
  14. Spring学习笔记之各个包的作用
  15. [ACM_数据结构] 线段树模板
  16. C# 非模式窗体show()和模式窗体showdialog()的区别
  17. 001-Spring的设计理念和整体架构
  18. maven 整合 ssm 异常分析
  19. springboot数据库操作及事物管理操作例子
  20. 使用pipework将Docker容器配置到本地网络环境中

热门文章

  1. Python中的绝对路径和相对路径
  2. python之元组,列表和字典的区别
  3. Python +selenium之集成测试报告与unittest单元测试
  4. UVA 11093 Just Finish it up 环形跑道 (贪心)
  5. [论文理解] CornerNet: Detecting Objects as Paired Keypoints
  6. PAT (Basic Level) Practise (中文)- 1007. 素数对猜想 (20)
  7. JQuery EasyUI学习记录(五)
  8. nodejs个人博客系统
  9. lua调用java过程
  10. (71)Received empty response from Zabbix Agent问题解决