2009年10月14日 21:36 阅读(55) 评论(2) 分类：program 《Dijkstra堆优化》

乱了我一个晚上的死东西终于写出来啦哈哈哈哈哈哈啊哈哈啊哈哈哈哈哈

果然调试的时候F7到某阶段再结合数据比较好调= =
这样比较具体思维不抽象比较好想
不过这样的话需要强大的出数据能力
就这点来说我现在弱了不少
真不应该

下面贴代码
d[i]表示点1到点i的距离
k[i]表示d[i]里面存的是哪一个点
b[i]表示点i存在d的哪一个位置


type data=record
      i:integer;
      d:longint;
     end;
var a:array[1..10000,1..100]of data;
    c,b,k:array[1..10000]of integer;
    d:array[1..10000]of longint;
    n:integer;
procedure init;
  var i,m,x,y,z:integer;
  begin
   fillchar(c,sizeof(c),0);
   readln(n,m);
   for i:=1 to m do
     begin
      readln(x,y,z);
      inc(c[x]);
      a[x,c[x]].i:=y;
      a[x,c[x]].d:=z;
      inc(c[y]);
      a[y,c[y]].i:=x;
      a[y,c[y]].d:=z;
     end;
  end;
procedure heap(x,n:integer);
  var j,z,z1,z2:integer;
  begin
   z:=d[x];z1:=k[x];
   while x
     begin
      j:=x*2;
      if (jd[j+1]) then inc(j);
      if z>d[j] then
        begin
         d[x]:=d[j];
         k[x]:=k[j];
         b[k[j]]:=x;
         x:=j;
        end
       else break;
     end;
   d[x]:=z;
   k[x]:=z1;
   b[z1]:=x;
  end;
procedure inst(x:integer);
  var z,z1:integer;
  begin
   z:=d[x];z1:=k[x];
   while (x>1)and(d[x]
     begin
      d[x]:=d[x shr 1];
      k[x]:=k[x shr 1];
      b[k[x shr 1]]:=x;
      x:=x shr 1;
     end;
   d[x]:=z;
   k[x]:=z1;
   b[z1]:=x;
  end;
procedure dijk;
  var i,j,x,x1,z,z1,z2:integer;
  begin
   for i:=1 to n do k[i]:=i;
   for i:=1 to n do b[i]:=i;
   for i:=1 to n do d[i]:=9999;
   d[1]:=0;
   for i:=1 to n do
     begin
      x:=d[1];x1:=k[1];
      z:=d[1];d[1]:=d[n-i+1];d[n-i+1]:=z;
      z:=b[k[1]];b[k[1]]:=b[k[n-i+1]];b[k[n-i+1]]:=z;
      z:=k[1];k[1]:=k[n-i+1];k[n-i+1]:=z;
      heap(1,n-i);
      for j:=1 to c[x1] do
        begin
         if x+a[x1,j].d
           begin
            d[b[a[x1,j].i]]:=x+a[x1,j].d;
            inst(b[a[x1,j].i]);
           end;
        end;
     end;
  end;
procedure outp;
  var i:integer;
  begin
   for i:=1 to n do write(d[b[i]],' ');
  end;
begin
 init;
 dijk;
 outp;
end.