二维/分层图模版题解(例题：传送门)

using namespace std;
#define maxx 11454810
#define N 10011
int dis[N][30]={0},head[100000];
int flag[N][30];
int n,m,k,f,cnt=0,p;

int tim[100000]={0};
int ans[100000]={0};
int w[100000]={0};
int ei;
struct edge{
	int to,w,next=0;
}e[100000];

struct df{
	int x,t,dis;
};
bool operator<(const df & a,const df & b)
{
	if(a.dis==b.dis)
	{
		return a.t>b.t;
	}
	else
	{
		return a.dis>b.dis;
	}
}
priority_queue<df>q;

void Shion()
{
	for(int i=0;i<=N-1;i++)
	{
		for(int j=0;j<=25;j++)
		{
			dis[i][j]=0x7fffffff;
		}
	}
	dis[1][0]=0;
	q.push(df{1,0,0});
	flag[1][0]=1;
	while(!q.empty())
	{
		df tmp=q.top();
		int x=tmp.x,t=tmp.t;
		q.pop();
		flag[x][t]=1;  //?
		
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(!flag[y][t]&&dis[y][t]>dis[x][t]+e[i].w) //不使用
			{
				dis[y][t]=dis[x][t]+e[i].w;
				if(!flag[y][t])
				{
					q.push(df{y,t,dis[y][t]});  
				}
			}
			if(t<k)
  				if(!flag[y][t+1]&&dis[y][t+1]>dis[x][t])//使用
				{
					dis[y][t+1]=dis[x][t];
					if(!flag[y][t+1])
					{
						q.push(df{y,t+1,dis[y][t+1]});
					}
				}
		}
	}
}
void add(int u,int v,int w) //起点u, 终点v, 权值w
{	
	cnt++;
	e[cnt].next=head[u];
	e[cnt].to=v;
	e[cnt].w=w;
	head[u]=cnt;
}
signed main()
{	
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	Shion();
	int minn=0x7fffffff;
	for(int i=0;i<=k;i++)
	{
		if(dis[n][i]<minn)
		{
			minn=dis[n][i];
		}
	}
	cout<<minn;
}