前言：

什么是分层图呢？请自行度娘。

什么时候用呢？当这个图可以改变一些路径的长度，或者一些状态（这个就需要在题目里面体会了）。

但是要注意，分层图对时间和空间的要求很高，所以当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;
}