백준 5719번 거의 최단 경로

< 백준 5719번 거의 최단 경로 - 마포 코딩박 >

사용한 알고리즘: 다익스트라


 단방향 간선들이 주어지고, 출발점에서 도착지점까지 가는 거의 최단 경로값을 출력하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (생각)
 먼저 다익스트라를 통해 최단경로에 쓰이는 간선을 찾아 체크해줍니다.
 이후 다익스트라를 한번 더 돌리는데, 앞서 체크된 사용한 간선은 사용하지 않습니다. 이는 거의 최단 경로가 될 것입니다.

(2) (코드 47~84)
 입력되는 간선정보를 토대로 다익스트라를 돌려 최단경로와 이때 쓰이는 간선을 저장합니다.

(2) (코드 85~87)
 과정(2)에서 저장한 간선들을 bool 배열로 체크해줍니다.

(3) (코드 88~112)
 최단경로에 쓰인 간선들을 제외한 간선들로 다익스트라를 한번 더 돌려서 거의 최단 경로값을 찾습니다.