O（2n^2）先统计从1到各个点的最短路径，在把每一条路方向翻转，再做一次Dijkstra。var d:array[1..10000] of longint; a,b:array[1..1000,1..1000] of longint; mark:array[1..10000] of boolean; n,t,c,i:longint;PRocedure dij(v0:longint);var j,u,min:longint;begin fillchar(mark,sizeof(mark),false); mark[v0]:=true; for i:=1 to n do d[i]:=a[v0,i]; repeat u:=0;min:=maxint; for i:=1 to n do if (not mark[i])and(d[i]<min) then begin u:=i; min:=d[i]; end; if u<>0 then begin mark[u]:=true; for i:=1 to n do if (not mark[i])and(d[u]+a[u,i]<d[i])then begin d[i]:=d[u]+a[u,i]; end; end; until u=0;end;procedure dij2(v0:longint);var j,u,min:longint;begin fillchar(mark,sizeof(mark),false); mark[v0]:=true; for i:=1 to n do d[i]:=b[v0,i]; repeat u:=0;min:=maxint; for i:=1 to n do if (not mark[i])and(d[i]<min) then begin u:=i; min:=d[i]; end; if u<>0 then begin mark[u]:=true; for i:=1 to n do if (not mark[i])and(d[u]+b[u,i]<d[i])then begin d[i]:=d[u]+b[u,i]; end; end; until u=0;end;procedure init;var x,y,z:longint;begin readln(n,t); for i:=1 to t do begin readln(x,y,z); if z<a[x,y] then a[x,y]:=z; if z<b[y,x] then b[y,x]:=z; end;end;begin fillchar(a,sizeof(a),$7f); fillchar(b,sizeof(b),$7f); init; dij(1); for i:=2 to n do c:=c+d[i]; fillchar(d,sizeof(d),0); dij2(1); for i:=2 to n do c:=c+d[i]; writeln(c);end.
