Poj2449 第K短路 — A*+Heap+Spfa

Note: 本文最初于 2011年 在 hi.baidu.com/lydrainbowcat 发表。

首先介绍一下启发式搜搜的A*算法：š

A*算法给每个状态进行一次评估，每次取出“当前实际代价+未来预期代价”最小的状态进行扩展。

š因此我们可以用一个二叉堆来保存这些状态，以实现取出最小值、插入新状态等操作。

šA*算法第一次从堆中把终态作为最小值取出时，就找到了最优解。

š

šA*算法核心在于设计预期未来代价的“估价函数”，设计标准是估计值不劣于未来的实际值。

š若估计值劣于未来实际值，则有可能本来在最优解搜索路径上的状态被错误地估计了较差的值，导致非最优解的搜索路径上的状态在最优解之前被取出，答案错误。

š若估计值优于未来实际值，则仅仅是在最优解取出之前多搜索了一些状态，在此基础上A*算法一定正确，估价越接近未来实际值，效率越高；估价为0时，退化为普通的搜索。

 

回到本题，š题意：有若干个询问，每次询问图中从a到b的可重复第k短路的长度。

解法：

š首先在反向图上使用Spfa或Dijkstra求出所有点到终点的最短路径。

š估价函数：当前走过的距离+该点到终点的最短路长度。

š用堆(优先队列)维护，每次取出估价函数最小的一个点扩展。

š第几次从堆中取出点u，就是找到了u的第几短路。

š第K次取出终点时程序结束。

Source Code

Problem: 2449		User: lydliyudong
Memory: 24608K		Time: 407MS
Language: Pascal		Result: Accepted

• Source Code

var
 head,next,head2,next2:array[0..100010]of longint;
 link:array[0..100010]of record x,y,z:longint; end;
 dis,d:array[0..1000]of longint;
 v:array[0..1000]of boolean;
 f,q:array[0..5000000]of longint;
 n,m,k,s,e,ans,i,t,tot:longint;

procedure scanf;
 var
  i,x,y,z:longint;
 begin
  readln(n,m);
  for i:=1 to m do
   begin
    readln(x,y,z);
    inc(tot);
    link[tot].x:=x; link[tot].y:=y; link[tot].z:=z;
    next[tot]:=head[x];
    head[x]:=tot;
    next2[tot]:=head2[y];
    head2[y]:=tot;
   end;
  readln(s,e,k);
  if s=e then inc(k);
 end;

procedure spfa;
 var
  l,r,i,x,j:longint;
 begin
  filldword(dis,sizeof(dis)div 4,maxlongint div 100);
  l:=1; r:=1;
  q[l]:=e; dis[e]:=0; v[e]:=true;
  while l<=r do
   begin
    x:=q[l];
    j:=head2[x];
    while j<>0 do
     begin
      if dis[link[j].x]>dis[x]+link[j].z then
       begin
        dis[link[j].x]:=dis[x]+link[j].z;
        if not v[link[j].x] then
         begin
          v[link[j].x]:=true;
          inc(r);
          q[r]:=link[j].x;
         end;
       end;
      j:=next2[j];
     end;//while j<>0
    v[x]:=false;
    inc(l);
   end;
 end;

procedure swap(var x,y:longint);
 var
  p:longint;
 begin
  p:=x; x:=y; y:=p;
 end;

procedure insert(p:longint);
 var
  x:longint;
 begin
  while p>1 do
   if f[p]+dis[q[p]]<f[p div 2]+dis[q[p div 2]] then
    begin
     swap(f[p],f[p div 2]);
     swap(q[p],q[p div 2]);
     p:=p div 2;
    end
   else break;
 end;

procedure heapify(l,r:longint);
 var
  t,p:longint;
 begin
  t:=l*2;
  while t<=r do
   begin
    if (t<r)and(f[t]+dis[q[t]]>f[t+1]+dis[q[t+1]]) then inc(t);
    if f[l]+dis[q[l]]>f[t]+dis[q[t]] then
     begin
      swap(f[l],f[t]);
      swap(q[l],q[t]);
      l:=t; t:=2*l;
     end
    else break;
   end;
 end;

procedure A_star;
 var
  i,x,now,j:longint;
 begin
  fillchar(q,sizeof(q),0);
  t:=1; q[1]:=s;
  while (d[e]<k)and(t>=1) do
   begin
    now:=q[1];
    inc(d[now]);
    if d[e]=k then begin ans:=f[1]; break; end;
    if d[now]<=k then
     begin
      j:=head[now];
      while j<>0 do
       begin
        if d[link[j].y]<k then
         begin
          inc(t);
          q[t]:=link[j].y;
          f[t]:=f[1]+link[j].z;
          insert(t);
         end;//if
        j:=next[j];
       end;//while
     end;//if
    q[1]:=q[t]; f[1]:=f[t]; dec(t);
    heapify(1,t);
   end;//while
 end;

begin
 scanf;
 spfa;
 A_star;
 if d[e]=k then writeln(ans)  else writeln(-1);
end.