学习笔记——分层图
分层图
刚听到这个思想的时候，蒟蒻实际上是被唬住了，后来学懂了发现
不过如此啊！！！
分层图求最短路
分层图的引入问题是这样的：
假设你要从图中的A点走到B点，并且你有k次机会免费走过某条边，那么请问最短路有多大？
这个问题可以拿动态规划解决，不过我们先看如何用分层图解决这个问题。
我们建k+1层图。然后有边的两个点，多建一条到下一层边权为0的单向边，如果走了这条边就表示用了一次机会。
对于数据：
n = 4，m = 3， k = 2
0 1 100
1 2 100
2 3 100
如下图
这个分层图共有k+1层n（k+1）个节点，我们只需要对这个分层图跑一遍最短路,输出3,3+n，3+2n，3+3n最小的值就可以了。
其他的问题都可由这个问题转化得到思路
动态规划求解
这里只是简单提一句动态规划，我们可以把dis与vis数组再开一维表示用了几次机会
dis[ i ][ j ] 代表到达 i 用了 j 次免费机会的最小花费.
vis[ i ][ j ] 代表到达 i 用了 j 次免费机会的情况是否出现过.
那么
不使用机会 dis[v][c] = min（min，dis[now][c] + edge[i].w）;
使用机会 dis[v][c+1] = min（dis[v][c+1]，dis[now][c]）;
上面都是裸的分层图
Luogu P3953
就是这道题吸引我学分层图的！！！