Hackerrank：ジャックは歓喜直観、修正Dijsktras

Question

問題文に行く：ソリューションのhttps://www.hackerrank.com/challenges/jack-goes-to-rapture

1つの使用は、ダイクストラのアルゴリズムを変更しています。

オリジナル：

修正

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 

私は（、距離（u）の重量（U、V））をALT =最大の後ろに直感を取得することはできませんよです最短経路内のエッジの最大重み。

誰かが解決策の背後にある直感を説明できますか？

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))