学步园

【题意】

给定一个r*c(r<=100,c<=100)的矩阵，每个元素表示该点高度，给定初始速度v，当从一点移动到另一点后，速度变为原先的2^(该点高度-移动到的点的高度)，花费时间是1/原先高度，求从1,1到r,c的最短时间

【输入】

第一行三个数v，r，c

接下来一个r*c的矩阵，意义如上（每个高度在[-25,25]）

【输出】

输出一个数表示从1,1到r,c的最短时间,保留两位小数

本来写了个heap+dijkstra，轻松地崩溃了

看了解析发现每个点的速度都是固定的，一遍spfa即可

program poj3037;
const
  zl:array [1..4,1..2] of longint=((0,1),(0,-1),(1,0),(-1,0));
  zero=1e-5;

var
  tot,r,c,i,j,k:longint;
  min,v:extended;
  h:array [0..101,0..101] of longint;
  dis,spd:array [0..101,0..101] of extended;
  x,y:array [0..2000001] of longint;

function quick (a,b:int64):int64;
var
  i:int64;
begin
  if b=0 then exit(1);
  if b=1 then exit(a);
  i:=quick(a,b div 2);
  if b and 1 = 1 then exit(i*i*a)
                 else exit(i*i);
end;

function change (a,b:longint):extended;
begin
  if a<b then exit(1/quick(2,b-a))
         else exit(quick(2,a-b));
end;

begin
  read(v,r,c);
  for i:=1 to r do
    for j:=1 to c do
      read(h[i,j]);
  tot:=0;
  for i:=1 to r do
    for j:=1 to c do
      spd[i,j]:=v*change(h[1,1],h[i,j]);
  for i:=1 to r do
    for j:=1 to c do
      dis[i,j]:=99999999999999999999999999;
  dis[1,1]:=0;
  tot:=1;
  i:=1;
  x[1]:=1;
  y[1]:=1;
  while i<=tot do
    begin
      for k:=1 to 4 do
        if (x[i]+zl[k][1]>=1)and(x[i]+zl[k][1]<=r)
        and(y[i]+zl[k][2]>=1)and(y[i]+zl[k][2]<=c) then
        if dis[x[i],y[i]]+1/spd[x[i],y[i]]<dis[x[i]+zl[k][1],y[i]+zl[k][2]] then
          begin
            dis[x[i]+zl[k][1],y[i]+zl[k][2]]:=dis[x[i],y[i]]+1/spd[x[i],y[i]];
            inc(tot);
            x[tot]:=x[i]+zl[k][1];
            y[tot]:=y[i]+zl[k][2];
          end;
      inc(i);
    end;
  writeln(dis[r,c]:0:2);
end.