최단 경로. [1238]

[1. 문제 설명]

https://www.acmicpc.net/problem/1238

---

[2. 풀이 접근]

단순하게 생각하면, 각 학생별로 파티가 열리는 곳 까지 다익스트라를 진행한 뒤,

파티가 열린 곳에서 각 학생 집까지 다익스트라를 진행하면 될 것 같은 문제이다.

그러나 이 방법은 다익스트라 알고리즘을 N 번 수행해야 한다.

(=> 대략 O(N*MLogN))

 

여차하면 시간 초과가 발생 할 수 있으며,

플로이드-워셜 사용을 고려 할 경우 역시 시간 초과가 발생 할 수 있다.

(=> O(N³), 이며, N 은 최대 1,000)

 

다익스트라 알고리즘의 아래와 같은 특성을 이용하는 문제이다.

• 출발지에서 모든 도착지 까지의 최단 경로를 구한다.

각 학생이 있는 마을에서 파티가 열리는 마을까지 최단 경로를 구하는 것이 아니라

목적지인 파티가 열리는 마을에서 출발지 들인 각 학생이 있는 마을까지 역방향으로 다익스트라 알고리즘을 진행하면

총 두번의 다익스트라 알고리즘을 수행하여 정답을 구할 수 있다.

 

역방향 다익스트라 탐색을 수행하기 위해서는 역방향 그래프 역시 필요하다.

---

[3. 코드]