【模板】A*算法，k短路

K短路问题是指我们在图中，寻找到从 s->t 的一条路径，并且该路径是所有 s->t 路径中能长度第k短的。

~个人认为是双向Dijsktra+剪枝~

算法核心

1. "减枝" 优化
2. 估价函数：g(x)=f(x)+w
3. Dijkstra最短路

"减枝" 优化

对于问题中所需要求的k短路，我们肯定是要多次访问某些节点的，所以我们会重复走某些边

而在普通的Dijkstra中我们是会 "减枝" 的，因为我们搜索时遇到了第一次进入该节点的时候，距离肯定是当前所有节点的最小值，那么当他最小值的时候往其他方向跑的距离肯定是最短的，后续再经过该节点的时候距离值肯定不会是最优的（因为路径值会一直增大）

同理，最短路（第1短路），只有第一次经过该节点的值有贡献，第k短，就是前k次经过节点的路径值有贡献，其他的路径值都是无用贡献。

如下图：

如果我们要从1->4,的前k小，那么肯会多走2<->3这条路，并且2节点最多经过4次，就可以了。

总结： 前k次经过某个节点的值对答案有贡献，后续就不需要经过该节点了。这种做法就把某些情况给剪掉了。

估价函数：g(x)=f(x)+w

含义： 假如我们已经到了某个点并且已经跑了w的距离，而为了能更快的到t点，我们会记录一个 估计函数f(x),该函数记录的是该点到t点的最短路径，然后实现过程我们跑g(x)最小值。

原因： 因为我们要跑图的时候，可能会出现：当前已走的距离较短，但是该点跑到t点的距离较长，如下图情况：

在该图中，1->2 、 1->3 、 2<->3；这几条路径的值都很小，如果按照传统的思路，我们每次都走当前能走的距离的最短的话，那么肯定会在某些节点反复横跳。

为了避免这种情况，我们排序的时候同时考虑估计函数f(x)，也就是我们每次排序都是 当前走的距离+当前节点到目的地的最短距离，这样就能优化掉反复横跳的情况。

解决方法： Dijkstra跑反图，并且"起点"是我们要的终点

总结： 当前走的距离+当前节点到目的地的最短距离进行排序。

code

void dijkstra(){
  memset(f,inf,sizeof(f));
  priority_queue<node1>q;
  q.push( { t,0 } );
  f[t]=0;
  while( !q.empty() )
  {
    node1 l=q.top();
    q.pop();
    int y=l.to,w=l.w;
    if( vis[y] ) continue;
    vis[y]=1;
    for(int i=head2[y];i;i=edge2[i].nex)
    {
      int x=edge2[i].to;
      if( f[x]>f[y]+edge2[i].w )
      {
        f[x]=f[y]+edge2[i].w;
        q.push( { x,f[x] } );
      }
    }
  }
}

Code

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1012,M=100012,inf=0x3f;
int n,m,f[N],cnt,tot,head1[N],head2[N];
int s,t,k,num[N];
bool vis[N];
struct {
  int to,nex,w;
}edge1[M],edge2[M];

struct node1{
  int to,w;
  bool operator < (const node1 &other) const
  {
    return other.w<w;
  }
};

struct node2{
  int to,w;
  bool operator < ( const node2 &other ) const
  {
    return other.w+f[other.to]<w+f[to];
  }
};

void dijkstra(){
  memset(f,inf,sizeof(f));
  priority_queue<node1>q;
  q.push( { t,0 } );
  f[t]=0;
  while( !q.empty() )
  {
    node1 l=q.top();
    q.pop();
    int y=l.to,w=l.w;
    if( vis[y] ) continue;
    vis[y]=1;
    for(int i=head2[y];i;i=edge2[i].nex)
    {
      int x=edge2[i].to;
      if( f[x]>f[y]+edge2[i].w )
      {
        f[x]=f[y]+edge2[i].w;
        q.push( { x,f[x] } );
      }
    }
  }
}

int astart(){
  priority_queue<node2>q;
  q.push({s,0});
  while( !q.empty() )
  {
    node2 l=q.top();
    q.pop();
    int y=l.to,w=l.w;
    num[y]++;
    if( num[t]==k ) return w;
    for(int i=head1[y];i;i=edge1[i].nex)
    {
      int x=edge1[i].to;
      if( num[x]<k )
      {
        q.push( {x,w+edge1[i].w} );
      }
    }
  }
  return -1;
}

void addedge1(int u,int v,int w)
{
  cnt++;
  edge1[cnt].to=v;
  edge1[cnt].nex=head1[u];
  edge1[cnt].w=w;
  head1[u]=cnt;
}

void addedge2(int u,int v,int w)
{
  tot++;
  edge2[cnt].to=v;
  edge2[cnt].nex=head2[u];
  edge2[cnt].w=w;
  head2[u]=tot;
}

int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++)
  {
    int u,v,w;
    cin>>u>>v>>w;
    addedge1(u,v,w);
    addedge2(v,u,w);
  }
  cin>>s>>t>>k;
  if( s==t ) k++;
  dijkstra();
  cout<<astart();

}