题目大意： 把许多牛奶从x镇运到y镇，求最小总费用。
dijkstra: a[i,j]表示i到j的距离。 f[i]表示起点x到点i的最短距离。 m[i]表示i号节点是否加入过集合。 1.把能连接的2个城镇i,j，它们的权值加入到a[i,j]，记住！a[i,j]跟a[j,i]都要赋值，因为是无向图，线是双向的。 2.做dijkstra，每次找未加入集合的且最小的点加入集合，并以它为中心调整其他点的参数。 时间复杂度:O(N^2)
var m:array [0..2501] of boolean; a:array [0..2501,0..2501] of longint; f:array [0..2501] of longint; i,j,t,c,x,y,p,q,w:longint;PRocedure dijkstra; var i,j,u,min:integer; begin for i:=1 to t do f[i]:=a[x,i]; repeat u:=0; min:=maxint; 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; end;begin readln(t,c,x,y); fillchar(m,sizeof(m),false); fillchar(a,sizeof(a),$7f); for i:=1 to c do begin readln(p,q,w); a[p,q]:=w; a[q,p]:=w; end; dijkstra; writeln(f[y]);end.新闻热点
疑难解答
