【分层图】飞行路线

首先说明,分层图解决的是单源最短路问题.

什么是分层图?

我的理解是,在一张图中我可以利用有限的操作从原本的一个点跳到下一个点的时候花费更少的操作,但本质上还是原本的图.

此时我们就可以虚构一个新的图出来,实现这种操作.

对于此题，我们只需要理解题目要求： 首先就是他们可以免费在最多 k 种航线上搭乘飞机，那意味着我们可以在某个点花费0元到另一个点，而从此时，以后的点都是花费了一次，即我们考虑建立分层图。

相同的花费为一层，当到达0层的时候就没有机会再使用这个特权了。

当飞机在u点的时候，他到达的v点我们就可以花费一次免费机会到到另一层。

区别

在原本dijstra/SPFA算法中将各个点到起点的距离数组开层二维数组,我们每用一次有限的操作的时候,就跳到另一行去,并更新新行的内容,这样就实现了分层的效果.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+12,inf=0x7f7f7f7f;
int n,m,k,cnt,dis[N][20],s,t,head[N],u,v,w;
int ans=inf;
struct{
  int to,nex,w;
}edge[N];
struct node{
  int u,w,use;
  bool operator < ( const node &other ) const
  {
    return w>other.w;
  }
};

void addedge(int u,int v,int w)
{
  cnt++;
  edge[cnt].to=v;
  edge[cnt].nex=head[u];
  edge[cnt].w=w;
  head[u]=cnt;
}

priority_queue<node>q;

void dijstra(){
  q.push({s,0,0});
  dis[s][0]=0;
  while( !q.empty() )
  {
    node l=q.top();
    q.pop();
    int y=l.u,kk=l.use;
    for(int i=head[y];i;i=edge[i].nex)
    {
      int x=edge[i].to;
      int w=edge[i].w;
      //cout<<x<<endl;
      if( dis[x][kk]>w+dis[y][kk] )
      {
        dis[x][kk]=w+dis[y][kk];
        q.push( {x,dis[x][kk],kk} );
      }

      if( kk<k and dis[x][kk+1]>dis[y][kk]  )
      {
        dis[x][kk+1]=dis[y][kk];
        q.push( {x,dis[x][kk+1],kk+1} );
      }

    }
  }
}

int main(){
  cin>>n>>m>>k;
  cin>>s>>t;
  memset(dis,inf,sizeof(dis));
  while(m--)
  {
    cin>>u>>v>>w;
    addedge(u,v,w);
    addedge(v,u,w);
  }
  dijstra();
  for(int i=0;i<=k;i++)
    ans=min(ans,dis[t][i]);
  cout<<ans;
}