RainAir
My OI Blog
RainAir
分层图最短路

定义

分层图最短路问题,一般是指我们在可以进行分层的图上进行最短路。
一般模型是:
在图上,有k次机会可以直接通过一条边,问起点与终点之间的最短路径。
题目链接

分析

其实这一题我们用动态规划的思想看,用dist[i][k]表示免费了k次的最短路径
详细的转移请参考代码
然后跑最短路即可。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/112
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

分层图最短路
定义 分层图最短路问题,一般是指我们在可以进行分层的图上进行最短路。 一般模型是: 在图上,有k次机会可以直接通过一条边,问起点与终点之间的最短路径。 题目链接 分析 其实这一…
扫描二维码继续阅读
2018-03-11
标签
近期评论