POJ P3259 Wormholes

题意：f组数据，n个点，m条无向边，w条有向负权边，判断是否有负权回路。

bellman-ford： 因为数组开小一直WA~ 1.做N次松弛操作，中间不能做就退出。 2.判断当前解是否最优，不是最优就YES，否则NO。

时间复杂度:最优 O(KE) K是一个比N小很多的数 最坏O(NE)

var s,t,w,dis:array [0..5201] of longint; n,i,j,a,b,c,e:longint; function bellman_ford:boolean; var f,i,j:longint; begin for i:=1 to a do begin f:=0; for j:=1 to e do if dis[s[j]]+w[j]<dis[t[j]] then begin f:=1; dis[t[j]]:=dis[s[j]]+w[j]; end; if f=0 then break; end; for j:=1 to e do if dis[s[j]]+w[j]<dis[t[j]] then exit(true); exit(false); end; begin readln(n); for i:=1 to n do begin fillchar(dis,sizeof(dis),$7f); dis[1]:=0; e:=0; readln(a,b,c); for j:=1 to b do begin inc(e); readln(s[e],t[e],w[e]); s[e+1]:=t[e]; t[e+1]:=s[e]; w[e+1]:=w[e]; inc(e); end; for j:=1 to c do begin inc(e); readln(s[e],t[e],w[e]); w[e]:=0-w[e]; end; if bellman_ford then writeln('YES') else writeln('NO'); end; end.