Poj3635 Full Tank — 优先队列BFS

Note: 本文最初于 2011年02月24日 星期四 22:10 在 hi.baidu.com/lydrainbowcat 发表。

搜索不济，整日TLE，这也得剪枝，那也得优化。

一开始我想到的是枚举每个点加多少油，并扩展到下一个点加多少油，也就是在BFS的过程中枚举状态，用Heap维护一个优先队列，每次取出花费最小的点扩展，第一次扩展到终点时就为所求。

但是以上算法跑完大数据需要两秒。

于是我们寻求一种优化，在杜神牛的指引下，我改为每个点只枚举两种状态——不加油走人，或者只加一升油（如果还有加油空间就还让它在堆里待着，否则扔掉）。杜神牛说这样会快的原因是，也许有的状态（加X升油）比较劣，就能被及时地踢到堆底不再进行扩展了，并且极大减少了每次的分支数量，降低了“搜索图”中的边数。

P.S. 这道题整整纠结了大约6个小时……我最终发现狂TLE的原因是：BFS前对队列进行了清零操作！！！由于我开的队列为100万，每次清零花费了巨大的时间，于是去掉这句话立刻<500ms……

Source Code

Problem: 3635		User: lydliyudong
Memory: 12916K		Time: 516MS
Language: Pascal		Result: Accepted

• Source Code

type
 rec=record cost,oil,num:longint; end;
var
 a,b,d:array[0..1000,-1..1001]of longint;
 c:array[0..1001]of longint;
 q:array[0..1000000]of rec;
 n,m,x,y,z,i,s,e,t,ques:longint;

function max(x,y:longint):longint;
 begin
  if x>y then exit(x) else exit(y);
 end;

procedure insert(p:longint);
 var
  z:rec;
 begin
  z:=q[p];
  while p>1 do
   if z.cost<q[p>>1].cost then
    begin
     q[p]:=q[p>>1];
     p:=p>>1;
    end
   else break;
  q[p]:=z;
 end;

procedure heapify(l,r:longint);
 var
  t:longint;
  z:rec;
 begin
  t:=l<<1; z:=q[l];
  while t<=r do
   begin
    if (t<r)and(q[t].cost>q[t+1].cost) then inc(t);
    if z.cost>q[t].cost then
     begin
      q[l]:=q[t];
      l:=t; t:=l<<1;
     end
    else break;
   end;
  q[l]:=z;
 end;

procedure bfs;
 var
  i,j,p,u,o,v,k:longint;
 begin
  p:=1; d[s,0]:=0;
  q[1].num:=s; q[1].cost:=0; q[1].oil:=0;
  while (p>=1)and(q[1].num<>e) do
   begin
    u:=q[1].num; o:=q[1].oil;
    if (o<t)and(q[1].cost+c[u]<d[u,o+1]) then
     begin
      d[u,o+1]:=q[1].cost+c[u];
      inc(p);
      q[p].num:=u; q[p].oil:=o+1; q[p].cost:=q[1].cost+c[u];
      insert(p);
     end;
    for i:=1 to b[u,0] do
     begin
      v:=b[u,i];
      j:=o-a[u,v];
      if (j>=0)and(q[1].cost<d[v,j]) then
       begin
        d[v,j]:=q[1].cost;
        inc(p);
        q[p].num:=v; q[p].oil:=j; q[p].cost:=q[1].cost;
        insert(p);
       end;//if
     end;//for
    q[1]:=q[p]; dec(p);
    heapify(1,p);
   end;//while
 end;

begin
 readln(n,m);
 for i:=0 to n-1 do read(c[i]); readln;
 for i:=1 to m do
  begin
   readln(x,y,z);
   a[x,y]:=z; a[y,x]:=z;
   inc(b[x,0]); b[x,b[x,0]]:=y;
   inc(b[y,0]); b[y,b[y,0]]:=x;
  end;
 readln(ques);
 for i:=1 to ques do
  begin
   readln(t,s,e);
   if s=e then writeln(0)
   else begin
    fillchar(d,sizeof(d),127);
    bfs;
    if d[e,0]>=maxlongint>>1 then writeln('impossible') else writeln(d[e,0]);
   end;
  end;
end.