Codeforces Round #800 (Div. 2) E. Keshi in Search of AmShZ

Problem - E - Codeforces

노드 1에서 노드 n까지 가는데 걸리는 최대 시간을 최소로 단축시키는 문제다.

따라서 여행자 p는 최대 시간으로 노드 1에서 출발하여 노드 n까지 간다고 할 수 있다.

어떤 노드 x에서 인접한 노드가 a, b, c 3개가 있다고 가정해보자.

노드 a에서 노드 n까지 최단시간을 3

노드 b에서 노드 n까지 최단시간을 2

노드 c에서 노드 n까지 최단시간을 1

라고 하자.

다익스트라로 모든 노드에서 노드 n까지 가는데 걸리는 최단시간을 구할 때

노드 x에 접근하는 최초의 경로는 c일 것이다.

노드 x에서 c로 가려면 a로가는 경로와 b로가는 경로를 지워야 하므로

노드 x에서 c로 갈 때 걸리는 시간은 3이다.

다음에 접근하는 경로는 b이고 걸리는 시간은 2이다.

그다음으로 접근하는 경로는 a이고 걸리는 시간은 1이다.

따라서 어떤 노드의 out degree를 카운트해주고 다익스트라로 경로가 접근될 때마다

걸리는 시간을 out degree로 계산한 다음 out degree를 1 감소시켜주면 된다.