Hackerrank：Jack 去 Rapture Intuition，Modified Dijsktras

Question

问题陈述：https://www.hackerrank.com/challenges/jack-goes-to-rapture

其中一个解决方案是使用修改后的 Dijkstra 算法。

原文：

For a vertex u,
Forall vertices v, instead of updating the distance by,
alt = distance(u) + weight(u, v)
if(alt < distance(v)) distance(v) = alt

修改时间：

For a vertex u,
Forall vertices v, instead of updating the distance by,
alt = max(distance(u), weight(u, v))
if(alt < distance(v)) distance(v) = alt

我无法理解 alt = max(distance(u), weight(u, v)) 背后的直觉，它是最短路径中边的最大权重。

有人可以解释解决方案背后的直觉。

Answer 1

If a passenger travels from station A to station B, he only has to pay the difference between the fare from A to B and the cumulative fare that he has paid to reach station A [fare(A,B) - total fare to reach station A]. If the difference is negative, he can travel free of cost from A to B.

因此，edge(A, B)的实际权重为max(0, fare(A, B) - min_distance(A))。所以累积距离将是：

min_distance(A) + max(0, fare(A, B) - min_distance(A)) = max(min_distance(A), fare(A, B))

Hackerrank：Jack 去 Rapture Intuition，Modified Dijsktras

Hackerrank: Jack goes to Rapture Intuition, Modified Dijsktras

algorithm

dijkstra