博客内食用
分层图简介
分层图，顾名思义。是将原图按不同状态分为若干与原图连接方式相同的图层，图层之间以特定方式连接的一类建图方式。如果画成立体图，大概是这样的：
根据如上思路，可以发现分层图有以下的几个性质：
假设原图位于 0 {0} 0 层，总共有 k k k 层图。那么对于任意 i ∈ [ 1 , k ] i\in[1,k] i∈[1,k]，层 i i i 内的节点之间的连接方式与 0 {0} 0 层是完全相同的（与原图连接方式相同）；但是层与层之间的连接方式不一定相同，具体取决于题意
假设不考虑节点所在层，仅考虑它在原图上对应的编号。假设有一条无向边 ( S , V ) (S,V) (S,V)，那么这条边会有大于等于一个权值（图层之间以特定方式连接）
根据性质二，我们大致可以明白分层图的使用范围——当题目中允许对某一条边做有限次的边权更改时即可考虑使用分层图做。在建图方面，根据数据范围的大小大致可以分为两种——离散建边和直观建边。接下来对两种建图方式作简要介绍。
分层图建图
离散建图
优点：细节较少、代码量短
缺点：对于大部分图论的数据范围容易爆空间、离散化有时不够直观
空间（最劣情况）：数组均为一维。对于前向星，无向存边数组为 2 [ ( K + 1 ) M + K N 2 ] {2}[(K+1)M+KN^2] 2[(K+1)M+KN2]（ K K K 层与原图相同的边，各层每个点间互相连了一条双向边，有向边则折半）；对于前向星的头数组，需要 N K NK NK 的空间（ K K K 层，每层 N N N 个点），最短路长度的记录数组和节点判重数组同上。
这种建图方法相当于将所有的图存在同一维数组上。假设原图共 n n n 个节点，且原图为第 0 {0} 0 层，那么对于原图上编号为 i i i 的点，它在第 k k k 层上的对应点的编号就应是 i + k n i+kn i+kn。至此我们就得到了分层图节点之间的映射关系。
在建图时，我们只需要在读入时处理连边即可。前向星存图和最短路算法都是模板，直接写就好。
while (m--) {
int a, b, c;
cin >> a >> b >> c;
for (int i = 0; i <= k; i++) {
add(a + i * n, b + i * n, c); // 在当前层之内连正常边权的双向边
add(b + i * n, a + i * n, c);
if (i < k) {
add(a + i * n, b + (i + 1) * n, c / 2); // 当前层和下一层直接互相连一条特定边权的双向边（此处为边权折半的情况）
add(b + i * n, a + (i + 1) * n, c / 2);
}
}
}
直观建图（推荐）
优点：一般不会爆空间、当前节点的信息明确、直观易懂
缺点：数组是二维的，代码量较长、需要注意部分细节
空间（最劣情况）：一维无向图前向星数组，大小为 2 M K {2}MK 2MK，头数组如上；最短路记录数组、判重数组为二维，第一维 N N N、第二维 K K K。
这种建图方式是最保险的，空间超限的概率相比上边那个要小，而且层数信息的传递也较直观。建议使用这个方法存图。
读入时只需建立层内边即可，若需要实现层与层之间的转化，只需要在最短路算法里判断即可。因而空间是大幅度节省的。我们只需对最短路进行一番修改即可：
for (int i = h[id]; ~i; i = edges[i].ne) {
int j = edges[i].to;
if (dis + edges[i].w < dist[j][layer]) {
// 当前层内，正常的最短路
dist[j][layer] = dis + edges[i].w;
q.push((PIII) {
dist[j][layer], (PII) {
j, layer}});
}
if (layer < k && dis + edges[i].w / 2 < dist[j][layer + 1]) {
// 如果下一层的点可更新，那么转移到下一层
dist[j][layer + 1] = dis;
q.push((PIII) {
dist[j][layer + 1], (PII) {
j, layer + 1}});
}
}
分层图典例
洛谷 P4822 [BJWC 2012] 冻结
题目地址：P4822
题目难度：提高+/省选-
题目来源：北京 2012
题目背景：
“我要成为魔法少女！”
“那么，以灵魂为代价，你希望得到什么？”
“我要将有关魔法和奇迹的一切，封印于卡片之中„„”
在这个愿望被实现以后的世界里，人们享受着魔法卡片（SpellCard，又名符卡）带来的便捷。
现在，不需要立下契约也可以使用魔法了！你还不来试一试？
比如，我们在魔法百科全书（Encyclopedia of Spells）里用“freeze”作为关键字来查询，会有很多有趣的结果。
例如，我们熟知的 Cirno，她的冰冻魔法当然会有对应的 SpellCard 了。当然，更加令人惊讶的是，居然有冻结时间的魔法，Cirno 的冻青蛙比起这些来真是小巫见大巫了。
这说明之前的世界中有很多魔法少女曾许下控制时间的愿望，比如 Akemi Homura、Sakuya Izayoi、……
当然，在本题中我们并不是要来研究历史的，而是研究魔法的应用。
题目描述：
我们考虑最简单的旅行问题吧： 现在这个大陆上有 N N