题目大意： 求一个邮递员把信分别送到2~N的最短路，与他回到节点的最短路之和。
dijkstra: 题目是无向图并且要求求出来回最短路之和。 2.用dijkstra求1到其它点的最短路，再将每条边反向再求一次1到其它点的最短路，然后相加。 时间复杂度:O(N^2)
var m:array [0..1001] of boolean; a,b:array [0..1001,0..1001] of longint; f:array [0..1001] of longint; i,j,t,c,p,q,w,ans:longint;PRocedure dijkstra; var i,j,u,min:longint; begin fillchar(m,sizeof(m),false); for i:=1 to t do f[i]:=a[1,i]; repeat u:=0; min:=maxlongint; for i:=1 to t do if (not m[i]) and (f[i]<min) then begin u:=i; min:=f[i]; end; if u<>0 then begin m[u]:=true; for i:=1 to t do if (not m[i]) and (f[u]+a[u,i]<f[i]) then f[i]:=f[u]+a[u,i]; end; until u=0; for i:=2 to t do ans:=ans+f[i]; end;begin readln(t,c); for i:=1 to t do for j:=1 to t do begin a[i,j]:=maxlongint div 3; b[i,j]:=a[i,j]; end; for i:=1 to c do begin readln(p,q,w); if w<a[p,q] then a[p,q]:=w; if w<b[q,p] then b[q,p]:=w; end; dijkstra; a:=b; dijkstra; writeln(ans);end.新闻热点
疑难解答
