首页 > 代码库 > poj3259
poj3259
找最小路径是否有负环就好
#include<iostream> #include<cstring> using namespace std; struct node { int s,e,t; }; node path[5201]; bool bellmanford(int s,int sw,int v,int e) { bool flag; int weight[501],i; memset(weight,60,sizeof(weight)); weight[s]=sw; while(v--) { flag=1; for(i=1;i<=e;i++) { if(weight[path[i].e]>weight[path[i].s]+path[i].t) { flag=0; weight[path[i].e]=weight[path[i].s]+path[i].t; } } if(flag) return 0; } return 1; } int main() { int i,f,n,m,w; scanf("%d",&f); while(f--) { scanf("%d%d%d",&n,&m,&w); for(i=1;i<=2*m;i++) { scanf("%d%d%d",&path[i].s,&path[i].e,&path[i].t); i++; path[i].s=path[i-1].e; path[i].e=path[i-1].s; path[i].t=path[i-1].t; } for(;i<=2*m+w;i++) { scanf("%d%d%d",&path[i].s,&path[i].e,&path[i].t); path[i].t=-path[i].t; } if(bellmanford(1,0,n,i-1)) { printf("YES\n"); } else { printf("NO\n"); } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。