POJ 3259Wormholes（贝尔曼最短路）

本文主要是介绍POJ 3259Wormholes（贝尔曼最短路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：http://poj.org/problem?id=3259

由于spfa是贝尔曼算法的队列优化，于是贝尔曼算法被我完全忽视了。。现在才发现贝尔曼算法在判断负环方面还是挺有用的。。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>using namespace std;
int n, m, d[10000], maxint=1000000;
struct node
{int u, v, w;
}edge[10000];
void bfff()
{int i, j, flag, x;memset(d,maxint,sizeof(d));for(i=0;i<n-1;i++){flag=0;for(j=0;j<m;j++){if(d[edge[j].v]>d[edge[j].u]+edge[j].w){d[edge[j].v]=d[edge[j].u]+edge[j].w;flag=1;}}if(flag==0)break;}x=0;for(i=0;i<m;i++){if(d[edge[i].v]>d[edge[i].u]+edge[i].w){x=1;break;}}if(x)printf("YES\n");elseprintf("NO\n");
}
int main()
{int m1, m2, i, t, u, v, w;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m1,&m2);m=2*m1+m2;i=0;while(m1--){scanf("%d%d%d",&u,&v,&w);edge[i].u=u;edge[i].v=v;edge[i++].w=w;edge[i].u=v;edge[i].v=u;edge[i++].w=w;}while(m2--){scanf("%d%d%d",&u,&v,&w);edge[i].u=u;edge[i].v=v;edge[i++].w=-w;}bfff();}return 0;
}

这篇关于POJ 3259Wormholes（贝尔曼最短路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---