DP/최단거리 역추적. [11780]

[1. 문제 설명]

n 개의 도시가 있고,

a 도시에서 b 도시에 도착하는 m 개의 버스가 있으며,

각 버스는 한번 사용할 때 필요한 비용이 잇다.

 

모든 도시 쌍에 대해서 A -> B 로 가는데 필요한 비용의 최소값과

경로를 출력하도록 한다.

---

[2. 풀이 접근]

n 은 최대 100 이고, 모든 도시 쌍의 최단 경로를 구해야 하므로,

플로이드 워셜 알고리즘을 이용하도록 한다.

=> 플로이드 워셜 알고리즘의 시간복잡도:  O(N³)

 

플로이드 워셜 알고리즘 사용 후, 경로를 구해야 할 때는 아래와 같이 접근한다.

• u -> v 로 가는 경로보다 u -> k -> v 로 가는 경로가 최단이면, u 와 v 의 경유지 k 를 설정하도록 한다.
• u 와 k 사이의 경로와 k 와 v 사이의 경로를 합치면, 전체 u -> v 경로가 나온다.
• 위 과정을 재귀적으로 처리한다.

플로이드-워셜 알고리즘에 대한 자세한 정리는 아래를 참조하도록 한다.

https://testkernelv2.tistory.com/449

---

[3. 코드]