题意：

约翰一共有 N 个牧场.由 MM 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 1 出发到牧场 N 去给奶牛检查身体。

通过每条小径都需要消耗一定的时间。约翰打算升级其中 K 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 0。

请帮助约翰决定对哪些小径进行升级，使他每天从 1 号牧场到第 N 号牧场所花的时间最短。

题解：

参考题解“”
一直知道分层图，但是没用过，突然遇到一道分层图的网络流题目，发现自己忘了分层图咋实现，赶紧拿来一道分层图模板题做做
简单说说什么是分层图：
其实就是将一个平面的图重新建图，有好几层
具体的说每层图之间各自连边与原图一样，但是相邻的两层图之间根据原来的关系进行连边
虽然是多层图，但是用一维的关系就可以
比如：
当有3个点，3层图时
1对应的就是 1+n 和 1+2 * n
2对应的就是 2+n 和 2+2 * n
.....
当存在n个点，k层图时，
1对应的就是1+n * 0, 1+ n* 1......1+n * (k-1)
而且每一层的图都遵循只能从上面的图到下一层图，不能反过来
那建这么多层图的目的是什么呢？
你可以理解成是一种尝试，就比如本题，我们向下一层就代表改造一条道路
我们向下一层代表改造一条道路，我们不可能改造道路后再把它修回原来的样子


我们要建多少层？
有k次机会，不难想出，我们要建k+1层

代码：

#include<cstdio>
#include<queue>
#define read(x) scanf("%d",&x)//宏定义，个人习惯
#define INF 0x3f3f3f3f//伪极大值
using namespace std;
typedef pair<int,int> pii;//个人习惯
struct Node
{
    int head,dis;
}node[210100];//数组大小注意
struct Edge
{
    int to,len,next;
}edge[4200100];//数组大小注意
int n,m,k,u,v,w,cnt,ans=INF<<1;
void addEdge(int u,int v,int w)
{
    edge[++cnt]={v,w,node[u].head};
    node[u].head=cnt;
}
//链式前向星存图
void Dijkstra()
{
    for(int i=1;i<=n*(k+1);i++)
    {
        node[i].dis=INF;
    }
    //初始化时，要注意我们的点数已经不是n了，而是n*（k+1）
    node[1].dis=0;
    priority_queue<pii,vector<pii>,greater<pii> >q;
    //小根堆
    q.push({0,1});
    while(q.size())
    {
        pii tmp=q.top();
        q.pop();
        int d=tmp.first,u=tmp.second;
        if(d!=node[u].dis)continue;
        for(int e=node[u].head;e;e=edge[e].next)
        {
            int v=edge[e].to;
            if(node[v].dis>edge[e].len+d)
            {
                node[v].dis=edge[e].len+d;
                q.push({node[v].dis,v});
            }
        }
    }
}
//最短路板子不解释
int main()
{
    read(n),read(m),read(k);
    for(int i=1;i<=m;i++)
    {
        read(u),read(v),read(w);
        for(int j=0;j<=k;j++)
        {
            /*
            当j为0时，我们建立的是原图的边
            当j不为0时，我们建立的是分身的边
             */
            addEdge(u+j*n,v+j*n,w);
            addEdge(v+j*n,u+j*n,w);
            //上面两行是每层图之间，自身的点的连线，边权不变
            if(j==k)break;
            /*
            为什么当j==k时，要退出循环呢？
            因为如果j==k时，还建下面的边，那么就超出范围了
            可以自行感性理解一下
             */
            addEdge(u+j*n,v+(j+1)*n,0);
            addEdge(v+j*n,u+(j+1)*n,0);
            //这两行建立的是层与层之间的边，边权为0
        }
    }
    Dijkstra();
    //跑最短路
    for(int i=0;i<=k;i++)
    {
        ans=min(ans,node[n+i*n].dis);
        //统计每一层到n距离的最小值
    }
    printf("%d\n",ans);
    //输出答案
    return 0;
}