poj3037

首先到每个点的速度实际上是一个定值，就是v0*2^(起点与当前点高度差）
所以当前点i到任意一个相邻点的时间都是一个定值，
不难想到构图最短路径
  1 const dx:array[1..4] of integer=(-1,1,0,0);
  2       dy:array[1..4] of integer=(0,0,-1,1);
  3       inf=999999999999;
  4 
  5 type link=^node;
  6      node=record
  7        po:longint;
  8        len:double;
  9        next:link;
 10      end;
 11      point=record
 12        num:longint;
 13        dis:double;
 14      end;
 15 
 16 var num,a:array[0..110,0..110] of longint;
 17     d:array[0..10010] of double;
 18     w:array[0..10010] of link;
 19     heap:array[0..10010] of point;
 20     where:array[0..10010] of longint;
 21     t,i,j,n,m,k,x,y:longint;
 22     v,vn,mid:double;
 23     p:link;
 24 
 25 procedure add(x,y:longint;c:double);
 26   var p:link;
 27   begin
 28     new(p);
 29     p^.po:=y;
 30     p^.len:=c;
 31     p^.next:=w[x];
 32     w[x]:=p;
 33   end;
 34 
 35 procedure swap(var a,b:point);
 36   var c:point;
 37   begin
 38     c:=a;
 39     a:=b;
 40     b:=c;
 41   end;
 42 
 43 function calc(x:longint):double;
 44   var i:longint;
 45   begin
 46     calc:=1;
 47     if x>0 then
 48     begin
 49       for i:=1 to x do
 50         calc:=calc*2;
 51     end
 52     else if x<0 then
 53     begin
 54       for i:=1 to abs(x) do
 55         calc:=calc/2;
 56     end;
 57   end;
 58 
 59 procedure sift(i:longint);
 60   var j,x,y:longint;
 61   begin
 62     j:=i shl 1;
 63     while j<=t do
 64     begin
 65       if (j+1<=t) and (heap[j].dis>heap[j+1].dis) then inc(j);
 66       if heap[i].dis>heap[j].dis then
 67       begin
 68         x:=heap[i].num;
 69         y:=heap[j].num;
 70         where[x]:=j;
 71         where[y]:=i;
 72         swap(heap[i],heap[j]);
 73         i:=j;
 74         j:=i shl 1;
 75       end
 76       else break;
 77     end;
 78   end;
 79 
 80 procedure up(i:longint);
 81   var j,x,y:longint;
 82   begin
 83     j:=i shr 1;
 84     while j>0 do
 85     begin
 86       if heap[i].dis<heap[j].dis then
 87       begin
 88         x:=heap[i].num;
 89         y:=heap[j].num;
 90         where[x]:=j;
 91         where[y]:=i;
 92         swap(heap[i],heap[j]);
 93         i:=j;
 94         j:=j shr 1;
 95       end
 96       else break;
 97     end;
 98   end;
 99 
100 begin
101   readln(v,n,m);
102   for i:=1 to n do
103   begin
104     for j:=1 to m do
105     begin
106       read(a[i,j]);
107       inc(k);
108       num[i,j]:=k;
109     end;
110   end;
111   for i:=1 to n do
112     for j:=1 to m do
113     begin
114       vn:=v*calc(a[1,1]-a[i,j]);
115       for k:=1 to 4 do
116       begin
117         x:=i+dx[k];
118         y:=j+dy[k];
119         if num[x,y]>0 then add(num[i,j],num[x,y],1/vn);
120       end;
121     end;
122 
123   n:=n*m;
124   t:=n;
125   for i:=1 to n do
126   begin
127     if i=1 then d[i]:=0 else d[i]:=inf;
128     heap[i].num:=i;
129     heap[i].dis:=d[i];
130     where[i]:=i;
131   end;
132   for i:=1 to n do
133   begin
134     x:=heap[1].num;
135     mid:=heap[1].dis;
136     if mid=inf then break;
137     y:=heap[t].num;
138     where[y]:=1;
139     swap(heap[1],heap[t]);
140     dec(t);
141     sift(1);
142     p:=w[x];
143     while p<>nil do
144     begin
145       y:=p^.po;
146       if d[y]>mid+p^.len then
147       begin
148         d[y]:=mid+p^.len;
149         k:=where[y];
150         heap[k].dis:=d[y];
151         up(k);
152       end;
153       p:=p^.next;
154     end;
155   end;
156   writeln(d[n]:0:2);
157 end.
View Code