: Dijsktras 수정 잭이 휴거 직관에 간다,

Question

문제 설명 : 솔루션의 https://www.hackerrank.com/challenges/jack-goes-to-rapture

하나는 사용이 다 익스트라의 알고리즘을 수정합니다.

가 원본 :

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 

내가 고도 = 최대 뒤에 직관을 얻을 수 아니다 (체중 거리 (유) (유, v)를)하는가이다 최단 경로에서 가장자리의 최대 무게.

누군가 해결책에 대한 직감을 설명해 줄 수 있습니까?

Answer 1

A 역에서 B 역으로 여행하는 승객은 A에서 B까지의 운임과 A 역에 도착하기 위해 지불 한 누적 운임 간의 차이 만 지불해야합니다 [운임 (A, B) - A 역에 도착하는 총 운임. 차이가 음수이면 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))