首页 > 其他分享 >分层图最短路

分层图最短路

时间:2023-02-09 16:47:58浏览次数:49  
标签:短路 平面图 分层 long 电梯 答案

板子题
双倍经验

分层图最短路 即为将一平面图建成立体分层的图 不同层间用“电梯”相连接
具体用途:对于可以选择修改路径长度的最短路

  • 能改几次就建几层的电梯 也就是说平面图要建 k+1 层

image
(偷个图 感谢 @Zimo_666 )

建图代码:
image

  • 一些需要注意的点:
    1.链前建无向图开四倍边 有向图开两倍边
    2.\(n*(k+1)\) 可能爆int 必要时记得开long long
    3.答案为 dis[t+n*k]
    4.记得判 k>=m 此时答案为 0

标签:短路,平面图,分层,long,电梯,答案
From: https://www.cnblogs.com/Steven24/p/17105775.html

相关文章