Niuke: flight route (layered map + shortest path)

Cattle guest ： Flight path （ Hierarchical graph + shortest path ）

The question ：

A graph with edge weights , Seek from s To t The shortest distance , You can ignore k The weight of the edge .

$2<=n<=10000,1<=m<=50000,0<=k<=10$
Ideas ：

because k Very small , Think about it No To the hierarchical graph , Think of the original as k layer , Each floor is exactly the same , Build new edges to connect each floor , For the first layer from x To y, hold x The point corresponding to each layer and the point corresponding to the next layer y Even one weight is zero 0 The edge of , hold y The point corresponding to each layer and the point corresponding to the next layer x Even one weight is zero 0 The edge of . So from a certain floor x To the next floor y It means you used it once k

Run the shortest path again

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
typedef pair<int,int>pii;
const int maxn=3e6+5;
int s,n,m,t,k,d,dis[maxn],vis[maxn],head[maxn],w[maxn],to[maxn],nex[maxn];
void add(int x,int y,int z){
    
	nex[++d]=head[x];
	to[d]=y;
	w[d]=z;
	head[x]=d;
}
void dij(){
    
	memset(dis,INF,sizeof(dis));
	dis[s]=0;
	priority_queue<pii,vector<pii>,greater<pii>>p;
	p.push({
    0,s});
	while(!p.empty()){
    
		int x=p.top().second;
		p.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=head[x];i;i=nex[i]){
    
			int y=to[i];
			if(dis[y]>dis[x]+w[i]){
    
				dis[y]=dis[x]+w[i];
				p.push({
    dis[y],y});
			}
		}
	}
}
int main(){
    
	scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
	for(int i=1,x,y,z;i<=m;i++){
    
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z),add(y,x,z);
		for(int j=1;j<=k;j++){
    
			add(x+j*n,y+j*n,z);
			add(y+j*n,x+j*n,z);
			add(x+(j-1)*n,y+j*n,0);
			add(y+(j-1)*n,x+j*n,0);
		}
	}
	dij();
	int ans=INF;
	for(int i=0;i<=k;i++){
    
		ans=min(ans,dis[i*n+t]);
	}
	printf("%d\n",ans);
}