这次的拆分约束有明显的起点。
拆分等式 Xb-Xa<=C
Xa-Xb<=-C
Program P3169; const maxml=10000; maxn=1000; var n,ml,md,i,j:longint; a,b:array[1..maxml,1..3] of longint; d:array[0..maxn] of longint; flag:boolean; procedure relax(v,u,w:longint); begin if d[v]>d[u]+w then begin d[v]:=d[u]+w; flag:=true; end; end; procedure bellman_ford; var i,j,k:longint; begin fillchar(d,sizeof(d),127); d[1]:=0; for k:=1 to ml+md do begin flag:=false; for i:=1 to ml do begin relax(a[i,2],a[i,1],a[i,3]); end; for i:=1 to md do begin relax(b[i,1],b[i,2],-b[i,3]); end; if not(flag) then break; end; if flag then writeln('-1') else if d[n]=2139062143 then writeln('-2') else writeln(d[n]); end; begin read(n,ml,md); for i:=1 to ml do begin read(a[i,1],a[i,2],a[i,3]); end; for i:=1 to md do begin read(b[i,1],b[i,2],b[i,3]); end; bellman_ford; end.