BOJ 17096

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

 

코드

http://boj.kr/1465a10980c64389892baa5e346c81c4

 

난이도 : P3

 

Elapse Time : 15min

 

문제에서 $N$과 $M$의 범위를 보니 다익스트라 문제임이 분명해 보였다. 일단 $i$번째 도시를 가는 데 최단경로로 이동해야 하고 경로가 여러 개라면 앞서 사용했던 경로를 최대한 재활용해야 한다. 우선 무지성으로 다익스트라를 짰는데 다익스트라 코드를 보면서 한 첫 번째 관찰은 특정 도시까지의 최단 거리는 항상 이전 노드까지의 최단 거리와 이전 노드와 현재 노드를 잇는 도로의 걸리는 시간의 합으로 표현된다는 것이다. 두 번째로 한 관찰은 $i$번째 도시를 방문할 경로가 정해져 있다면 방문하는 순서와는 무관하게 답이 결정된다는 것이다. 두 가지를 조합해 보니 다익스트라 코드에서 $pq$에서 노드가 나오는 순서를 방문 순서로 설정할 경우 다익스트라 코드를 조금만 변형하면 답을 구할 수 있다는 것이다. 다익스트라에서 최단경로 대신 최단경로와 도달 직전 도로의 걸리는 시간을 pair로 묶어 관리해주면 모든 노드에 대해 도달 직전 도로의 걸리는 시간의 합이 답이 된다.