【Remmarguts' Date】

一道来自POJ2449的题，它融合了单源点最短路算法、启发式搜索，让我们对“启发式”有更深的理解和体会。Wow！

·英文题，述大意：

读入n,m(n<=1000,m<=100000)，表示节点数和边数，接下来m行输入每条有向边的端点和权值。之后输入起点、终点和K。求出第K短路的长度，没有就输出-1.(注意：①一条起点到终点的路径上可以包含多个相同点，起点终点也可以包含多个!②起点和终点可以重合，而且最短路就是0)

·分析：

首先就是要搜索。不过搜索的判断依据要做变化，决不是以前简单的dis比大小了。说专业点就是尝试要构造启发式f()函数，说通俗点，就是尝试更改搜索队列的优先级关键字信息，使得满足条件。

在搜索里，由于不是找最短路，所以vis[]荡然无存。我们需要一种优先队列，使得当前弹出的是目前最短路。如何寻到第K短路：找到一条最短路，用cnt记一下，表示当前找到的起点到终点的第cnt短路，直至K==cnt。

美妙之处在于怎样快速找出当前搜索到的点中，顺着哪一个点先走下去会得到一条到终点的当前最短路。也就是我们要具有一种预测未来的能力，它不同于正常的最短路思路：不断尝试，不断贪心。预测未来能力能够知道按某一个点先开始展开搜索，它一定在未来先以最短路抵达终点。

我们不具有预测未来的能力，所以只能预处理。预处理以终点为单源点的最短路dis数组。那么在我们使用搜索的时候，只需要将起点到当前点距离与当前点和终点的最短路距离的和作为比较关键字存入优先队列中，这样一来每一步优先队列都为您维护着最有希望的那个点(the most promising point)。

在代码来到之前有一个申明：虽说vis数组已经不在了，但是大米饼依旧用它的名字在搜索中表示当前点被访问的次数（因为每个点最多被访问K次）

 #include<stdio.h>

 #include<queue>

 #include<cstring>

 #define go(i,a,b) for(int i=a;i<=b;i++)

 #define fo(i,a,x) for(int i=a[x],v=e[i].v;i;i=e[i].next,v=e[i].v)

 #define inf 100000000

 using namespace std;const int N=;struct E{int v,next,w;}e[N*N*];

 struct Kth{int u,f;bool operator<(const Kth& a)const{return f>a.f;}};

 int n,m,head[N],back[N],k=,S,T,K,dis[N],ans=-;

 void ADD(int u,int v,int w,int* H){e[k]=(E){v,H[u],w};H[u]=k++;}

 void SPFA()

 {

     queue<int>q;bool inq[N]={};go(i,,n)dis[i]=inf;dis[T]=;q.push(T);

     while(!q.empty())

     {

         int u=q.front();q.pop();inq[u]=;

         fo(i,back,u)if(dis[u]+e[i].w<dis[v]){

         dis[v]=dis[u]+e[i].w;!inq[v]?q.push(v),inq[v]=:;}

     }

 }

 void BFS()

 {

     if(dis[S]>=inf)return;priority_queue<Kth>q;

     int vis[N]={};q.push((Kth){S,dis[S]});K+=S==T;

      while(!q.empty())

      {

          Kth p=q.top();q.pop();int u=p.u;vis[u]++;

          if(vis[T]==K){ans=p.f;return;}fo(i,head,u)if(vis[v]<K)

          q.push((Kth){v,p.f-dis[u]+e[i].w+dis[v]});

      }

 }

 int main(){scanf("%d%d",&n,&m);go(i,,m){int u,v,w;scanf("%d%d%d",&u,&v,&w);

     ADD(u,v,w,head),ADD(v,u,w,back);}scanf("%d%d%d",&S,&T,&K);

     SPFA();BFS();printf("%d\n",ans);return ;

 }//Paul_Guderian

巴特西

【Remmarguts' Date】

I love you!always!Tme is nothing——The Time Traveller,Henry

最新文章

热门文章