Hackerrank：杰克去狂喜的直觉，修改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的直觉（距离（U），重量（U，V）），这是最短路径中边缘的最大重量。

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

Answer 1

如果一个乘客从A站到B站，他只需支付A到B的票价和他到A站支付的累计票价之间的差额[票价（A，B） - 到达A站的总票价]。如果差值是负数，他可以免费从A到B旅行。

因此，边缘（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))