分层图的两种建法

1：实实在在的建图，n层

2：逻辑上的对图分层，一般就是给dis数组或者vis数组，总之就是你需要参与求解实际问题的数据结构额外增加一维数组来模拟n层的效果

例题：ACWing340通信线路

第一种：

优先队列 按照pair的第一个int按降序排列，所以路径设置为-w，但是无关紧要，它只提供选择顺序，真正修改的是dis数组，输出的也是dis数组的值。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+100,maxm = 1e7+10,maxk = 1e3+10;
int dis[maxn],vis[maxn];
int n,p,k;
int tot, head[maxn];
struct Edge{
	int to,nxt,w;
}e[maxm];
void add(int from,int to,int w)
{
	e[tot].to = to; e[tot].w = w; e[tot].nxt = head[from];
	head[from] = tot++;
}

priority_queue<pair<int, int> > q;
void dij()
{
	memset(dis,0x3f,sizeof(dis));
	dis[1] = 0;
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		int u = q.top().second; q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = head[u]; ~i; i = e[i].nxt)
		{
			int w = max(e[i].w,dis[u]);
			if(dis[e[i].to] > w)
			{
				dis[e[i].to] = w;
				q.push(make_pair(-w,e[i].to));
			}
		}
	}
}
int main()
{
	memset(head,-1,sizeof(head)); tot = 0;
	scanf("%d%d%d",&n,&p,&k);
	for(int i = 0, a, b, c; i < p; ++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c); add(b,a,c);
		for(int j = 1; j <= k; ++j)
		{
			int x = a, y = b;
			add(x+(j-1)*n,y+j*n,0);
			add(y+(j-1)*n,x+j*n,0);
			add(x+j*n,y+j*n,c);
			add(y+j*n,x+j*n,c);
		}
	}
	for(int i = 1; i <= k; ++i) add(i*n,(i+1)*n,0);
	dij();
	if(dis[(k+1)*n] == 0x3f3f3f3f) puts("-1");
	else printf("%d\n",dis[(k+1)*n]);
	return 0;

}

第二种：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10,maxm = 1e5+10,maxk = 1e3+10;
int dis[maxn][maxk],vis[maxn];
int n,p,k;
int tot, head[maxn];
struct Edge{
	int to,nxt,w;
}e[maxm];
void add(int from,int to,int w)
{
	e[tot].to = to; e[tot].w = w; e[tot].nxt = head[from];
	head[from] = tot++;
}
queue<int> q;
void spfa(int s)
{
	memset(dis,0x7f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s][0] = 0;
	q.push(s);
	while(!q.empty())
	{
		int u = q.front(); q.pop(); vis[u] = 0;
		for(int i = head[u]; ~i; i = e[i].nxt)
		{
			int to = e[i].to, w = max(e[i].w,dis[u][0]);
			if(dis[to][0] > w)
			{
				dis[to][0] = w;
				if(!vis[to]) vis[to] = 1, q.push(to);
			}
			for(int p = 1; p <= k; ++p)
			{
				w = min(dis[u][p-1],max(dis[u][p],e[i].w));
				if(dis[to][p] > w)
				{
					dis[to][p] = w;
					if(!vis[to]) vis[to] = 1, q.push(to);
				}
			} 
		}
	}
}
int main()
{
	memset(head,-1,sizeof(head));; tot = 0;
	scanf("%d%d%d",&n,&p,&k);
	for(int i = 0, a, b, c; i < p; ++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c); add(b,a,c);
	}
	spfa(1);
	int ans = 1e9;
	for(int i = 0; i <= k; ++i) ans = min(ans,dis[n][i]);
	if(ans == 1e9) ans = -1;
	printf("%d",ans);
	return 0; 
}