我们首先知道,答案肯定是最短路图中的某段公共链,那么设(x,y)为x到y的最短路,那么答案为((s1,t1)+(s2,t2)-min((s1,s2)+(t1,t2),(s1,t2),(s2,t1))) div 2,这两种情况分别可以画成下面的图
这样就可以十分明显的看出了。因为中间的一段算了两遍,所以要div 2。
/************************************************************** Problem: 1880 User: BLADEVIL Language: Pascal Result: Accepted Time:2488 ms Memory:7900 kb ****************************************************************/ //By BLADEVIL var n, m :longint; s1, t1, s2, t2 :longint; pre, other, len :array[0..600010] of longint; last :array[0..2000] of longint; flag :array[0..2000] of boolean; vis :array[0..600010] of boolean; l :longint; dis, que :array[0..2000] of longint; d1, d2, d3, d4 :array[0..2000] of longint; ans :longint; function min(a,b:longint):longint; begin if a>b then exit(b) else exit(a); end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure connect(x,y,z:longint); begin inc(l); pre[l]:=last[x]; last[x]:=l; other[l]:=y; len[l]:=z; end; procedure init; var i :longint; x, y, z :longint; begin read(n,m,s1,t1,s2,t2); l:=1; for i:=1 to m do begin read(x,y,z); connect(x,y,z); connect(y,x,z); end; fillchar(vis,sizeof(vis),true); end; procedure spfa(x:longint); var q, p :longint; h, t, cur :longint; begin filldword(dis,sizeof(dis) div 4,maxlongint div 2); h:=0; t:=1; que[1]:=x; dis[x]:=0; while h<>t do begin h:=h mod 2000+1; cur:=que[h]; flag[cur]:=false; q:=last[cur]; while q<>0 do begin if vis[q] then begin p:=other[q]; if dis[p]>dis[cur]+len[q] then begin dis[p]:=dis[cur]+len[q]; if not flag[p] then begin t:=t mod 2000+1; que[t]:=p; flag[p]:=true; end; end; end; q:=pre[q]; end; end; end; procedure main; var ans1, ans2 :longint; tot1, tot2 :longint; i :longint; q, p :longint; begin spfa(s1); ans1:=dis[t1]; for i:=1 to n do d1[i]:=dis[i]; spfa(s2); ans2:=dis[t2]; for i:=1 to n do d2[i]:=dis[i]; spfa(t1); for i:=1 to n do d3[i]:=dis[i]; spfa(t2); for i:=1 to n do d4[i]:=dis[i]; fillchar(vis,sizeof(vis),false); for i:=1 to n do begin q:=last[i]; while q<>0 do begin p:=other[q]; if d1[i]+len[q]+d3[p]=ans1 then begin vis[q]:=true; vis[q xor 1]:=true; end; if d2[i]+len[q]+d4[p]=ans2 then begin vis[q]:=true; vis[q xor 1]:=true; end; q:=pre[q]; end; end; spfa(s1); tot1:=dis[s2]; tot2:=dis[t2]; spfa(t1); tot1:=tot1+dis[t2]; tot2:=tot2+dis[s2];; ans:=(ans1+ans2-min(tot1,tot2)) div 2; ans:=max(ans,0); writeln(ans); end; begin init; main; end.