计蒜客 A1958 – Magical Girl Haze

题目链接:计蒜客 A1958 – ICPC 2018 南京赛区网络赛 L题

这是一个经典的分层图最短路问题,模型是这样的:一张$n$个节点$m$条边的图(这一题是有向边),每条边都有对应的边权$c_i$,现在可以使用$k$次把当前边的边权变为$0$的权利,求$s$到$t$的最短路。

考虑$f(i,u)$表示起点到$i$点,使用了$u$次变零权利的最短路径。原来的Dijkstra算法每次从堆中取出点之后,会做一次判断并松弛,现在我们多做一次判断松弛,即讨论不使用变零权和使用变零权两种情况都做一次判断。

相比原来的Dijkstra算法,分层最短路把一维动态规划拓展成了二维动态规划,实质是一样的。渐进时间复杂度$\Theta(k(n+m) \log n)$。

 

1
说点什么

avatar
50
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 计蒜客 A1958 – Magical Girl Haze […]