POJ3259 Wormholes 【Bellmanford判断是否存在负回路】

本文主要是介绍POJ3259 Wormholes 【Bellmanford判断是否存在负回路】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

很简单的bellmanford题目，这里比较详细：http://blog.csdn.net/lyy289065406/article/details/6645790

直接代码

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int SIZE=11111;
const int MAXLEN=1<<30;
struct sss
{int s,e,v;
}ed[SIZE];
int N,M,WH;
int dis[SIZE];
int ednum;
bool Bellman()
{for(int i=0;i<N-1;i++){bool flag=false;for(int j=0;j<ednum;j++){if(dis[ed[j].e]>dis[ed[j].s]+ed[j].v){flag=true;dis[ed[j].e]=dis[ed[j].s]+ed[j].v;}}if(!flag)break;}for(int j=0;j<ednum;j++){if(dis[ed[j].e]>dis[ed[j].s]+ed[j].v){return true;}}return false;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("G:/1.txt","r",stdin);freopen("G:/2.txt","w",stdout);#endifint f,u,v,w;cin>>f;while(f--){ednum=0;cin>>N>>M>>WH;for(int i=0;i<SIZE;i++){dis[i]=MAXLEN;}for(int i=0;i<M;i++){cin>>u>>v>>w;ed[ednum].s=u;ed[ednum].e=v;ed[ednum++].v=v;ed[ednum].e=u;ed[ednum].s=v;ed[ednum++].v=w;}for(int i=0;i<WH;i++){cin>>u>>v>>w;ed[ednum].s=u;ed[ednum].e=v;ed[ednum++].v=-w;}if(Bellman())printf("YES\n");elseprintf("NO\n");}return 0;
}

 

这篇关于POJ3259 Wormholes 【Bellmanford判断是否存在负回路】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---