题解 P1339 【[USACO09OCT]热浪Heat Wave】

displaylzy · 2017-03-03 21:30:08 · 题解

题目大意：

把许多牛奶从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.