分层图最短路
偶然间看到了这个，正好没学过，感觉挺有意思的，于是就顺手写个了博客。
定义
顾名思义，“分层图最短路”就是在分层图上跑最短路。
模型
在图上，有k次决策，问起点与终点之间的最短路径。
k个决策不会影响图的结构，只会影响当前的代价或状态。
做法
一般有两种做法：
-
第一个方法：建 $k+1$ 的分层图。
-
第二个方法：多开一维的数组记录决策信息。
方法一
-
对于同一层的图，每一层都按原图建边。
-
对于相邻两层的图，若原图中从 $u$ 到 $v$ 有一条边，那么就从 $u$ 到下一层对应的 $v$ 连一条边，从 $v$ 到下一层的 $u$ 也连一条。边的权值取决于决策内容。
这样我们就通过建图模拟了 $k$ 次决策。
具体可参考下面这张图（引用于cyhyyds的博客）。
具体的建边过程如下：
for(int j=0;j<=k;j++){
//同一层建边
add_edge(u+j*n,v+j*n,w);
add_edge(v+j*n,u+j*n,w);
//两层间建边
add_edge(u+j*n,v+(j+1)*n,0);
add_edge(v+j*n,u+(j+1)*n,0);
}方法二
首先可以在原来的数组上多加一维来记录决策信息：
- $dis[i][j]$ 表示到达点 $i$ 进行了 $j$ 次决策时的最短路。
- $vis[i][j]$ 表示到达点 $i$ 进行了 $j$ 次决策时点 $i$ 是否访问过。
状态转移（$w$ 为边权）：
- $dis[v][k]=min(dis[v][k],dis[u][k]+w)$
- 可以进行决策时：$dis[v][k]=min(dis[v][k],dis[u][k-1]+w)$
在这种方法中，数组记录的进行了 $j$ 次决策，实际上也可以看做是在方法一中的图上到达了第 $j$ 层，两者是等价的，复杂度都为 $O(mklog(mk))$ 。
个人比较喜欢第一种，毕竟多加几句建个图直接套模板谁不喜欢呢。
练习
板子题。因为次数不一定要用完，所以答案要从每层终点的答案里取最小值。
P2939 [USACO09FEB]Revamping Trails G
双倍经验。
P1948 [USACO08JAN]Telephone Lines S
三倍经验？注意题目中的花费是路径边权最大值，要改一下最短路模板。
层之间的边权为原边权一半。
在这道题中的决策是买入或卖出或不买。只要建三层就够了，第一层到第二层代表买入，边权为 $-w$ ；第二层到第三次代表卖出，边权为 $w$ 。每一层内边权均为 0 。
本篇参考：