分层图最短路 即为将一平面图建成立体分层的图 不同层间用“电梯”相连接
具体用途:对于可以选择修改路径长度的最短路
- 能改几次就建几层的电梯 也就是说平面图要建 k+1 层
(偷个图 感谢 @Zimo_666 )
建图代码:
- 一些需要注意的点:
1.链前建无向图开四倍边 有向图开两倍边
2.\(n*(k+1)\) 可能爆int 必要时记得开long long
3.答案为 dis[t+n*k]
4.记得判 k>=m 此时答案为 0
分层图最短路 即为将一平面图建成立体分层的图 不同层间用“电梯”相连接
具体用途:对于可以选择修改路径长度的最短路
(偷个图 感谢 @Zimo_666 )
建图代码: