【洛谷1629】邮递员送信

2019-11-06 07:50:57

字体：大中小

来源：转载

供稿：网友

问题描述 有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。 样例输入 5 10 2 3 5 1 5 5 3 5 6 1 2 8 1 3 8 5 3 4 4 1 8 4 5 3 3 5 6 5 4 2 样例输出 83 算法讨论 这里因为每送一次要返回，所以做完一遍dijkstra后要把图反过来再做一遍，就等于找所有点到1的最短路。时间复杂度O(n²)。

const maxn=1000;var a:array[1..maxn,1..maxn] of longint; d:array[1..maxn] of longint; f:array[1..maxn] of 0..1; i,j,n,m,x,y,w,u,min,t:longint; s:int64;PRocedure dijkstra;begin f[1]:=1; for i:=1 to n do d[i]:=a[1,i]; repeat u:=0; min:=maxlongint; for i:=1 to n do if (f[i]=0) and (min>d[i]) then begin min:=d[i]; u:=i end; if u<>0 then begin f[u]:=1; for i:=1 to n do if (f[i]=0) and (d[i]>a[u,i]+d[u]) then d[i]:=a[u,i]+d[u] end; until u=0;end;begin read(n,m); fillchar(a,sizeof(a),$7f); for i:=1 to m do begin read(x,y,w); if a[x,y]>w then a[x,y]:=w end; dijkstra; for i:=2 to n do s:=s+d[i]; for i:=1 to n do for j:=i to n do begin t:=a[i,j]; a[i,j]:=a[j,i]; a[j,i]:=t end; fillchar(f,sizeof(f),0); fillchar(d,sizeof(d),0); dijkstra; for i:=2 to n do s:=s+d[i]; write(s)end.

这里写图片描述 Pixiv ID：61676992