【模板】分层图

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

什么是分层图?

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

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

区别

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

Code

#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;
}