前言：
什么是分层图呢？请自行度娘。
什么时候用呢？当这个图可以改变一些路径的长度，或者一些状态（这个就需要在题目里面体会了）。
但是要注意，分层图对时间和空间的要求很高，所以当k比较小的时候，才可以使用。
分层图的空间一定要算好，不要像我，每次分层图总是空间爆了，或者RE。
先给个模板代码（Luogu4568）
代码：
#include<bits/stdc++.h> using namespace std; struct edge { int v,w,nxt; }e[3001001]; int cnt,head[3001001]; void add(int u,int v,int w) { cnt++; e[cnt].v=v; e[cnt].w=w; e[cnt].nxt=head[u]; head[u]=cnt; } int dis[3001001]; bool vis[3001001]; struct node { int id,dis; bool operator < (const node &tt) const { return dis>tt.dis; } }; priority_queue<node> q; void dij(int s) { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]=0; q.push(node{s,0}); while(q.size()) { node uu=q.top(); int u=uu.id; q.pop(); if(vis[u]) continue ; vis[u]=1; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(dis[v]>dis[u]+e[i].w) { dis[v]=dis[u]+e[i].w; q.push(node{v,dis[v]}); } } } } int n,m,k,s,t; int main() { scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); for(int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); for(int j=1;j<=k;j++) { add(u+(j-1)*n,v+j*n,0); add(v+(j-1)*n,u+j*n,0); add(u+j*n,v+j*n,w); add(v+j*n,u+j*n,w); } } dij(s); int ans=INF; for(int i=0;i<=k;i++) ans=min(ans,dis[n+i*n]);//这个要注意！！！ cout<<ans; return 0; }
例题.
2939 水题
4822 水题
1948
讲实话我是用SPFA+二分过去的，但这题很明显可以用分层图。同样的建图，二分，如果e[i].w>x的，那么不能走这条路。最后判断一下，能否走到每一层的终点。如果不是用分层图，那就是如果这条路能走，那么w=0，否则为1，最后将cn[n]与k比较，从而得出，能否到达终点，分层图也可以这样，就是最后的判断改一下而已。
1073【NOIP2009】提高组
很多人是缩点加SPFA，反正我不会，商人肯定是先去到自己要买的地方，再想办法去自己要卖的地方，最后去终点，并不是最短路，也就是有三种状态，那么建三层图。
如果从第一层下来，说明在此买了，如果从第二层下来，说明卖了，除了层之间的边，其余边为0，最后求最大值。
这个题这个做法还是很精妙的。
代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; const int INF=10000000; int n, m, dis[maxn*3], vis[maxn*3]; vector<pair<int, int> > G[maxn*3]; #define t(x,i) (x+i*n) #define add(x, y) G[t(x,0)].push_back({t(y,0), 0}), G[t(x,1)].push_back({t(y,1),0}), G[t(x,2)].push_back({t(y,2),0}) void spfa(int s) { for(int i = 1;i <= n*3;i++) dis[i] =-INF; dis[s] = 0; queue<int> q; vis[s]=1; q.push(s); while(!q.empty()) { int x = q.front(); q.pop(); vis[x] = 0; for(int i=0;i<G[x].size();i++) { int v=G[x][i].first; if(dis[v] < dis[x] + G[x][i].second) { dis[v] = dis[x] + G[x][i].second; if(!vis[v]) { q.push(v); vis[v] = 1; } } } } } int main() { cin >> n >> m; for(int i = 1, v;i <= n; ++i) { cin >> v; G[t(i,0)].push_back({t(i,1), -v}); G[t(i,1)].push_back({t(i,2), v}); } for(int i = 1,x,y,z;i <= m; ++i) { cin >> x >> y >> z; add(x, y); if(z == 2) add(y, x); } spfa(t(1,0)); cout << dis[t(n,2)] << endl; return 0; }