第3题-巡检车最短补油用时 - problem_ide - CodeFun2000

登录查看题面

登录后即可查看完整题面内容。

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（拼多多机考题库），可解锁完整内容。

购买题库开通会员

解题思路

油箱容量不大，把「在哪个站、还剩多少油」当成状态，按时间做最短路。

状态 $(u,f)$ 表示在站点 $u$ 、剩余油量 $f$ 。出发是 $(1,q)$ ，时间为 $0$ 。
两种转移：在本站补 1 单位油，到 $(u,f+1)$ ，加时 $r_u$ ；或者走一条耗油不超过 $f$ 的公路，到对面站点并扣油，加时为路耗时。
用堆优化的最短路更新这些状态。到达 $k$ 号站时，所有剩余油量里的最小时间就是答案；一次都到不了则是 -1。

复杂度分析

编辑器加载中…

输入

预期输出（选填）