[백준 5719] 거의 최단 경로

멈춰!

 

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

5719번: 거의 최단 경로

[백준 5719] 거의 최단 경로 (platinum 5)

 

거의 최단 경로 문제는 최단경로를 제외한 경로들 중 가장 짧은 경로를 찾아 그 길이를 출력하는 문제입니다.

최단 경로를 알아내는 과정이 여러번 필요할 것으로 예상되므로, 최단 경로 알고리즘 중 저에게 가장 익숙한 다익스트라 알고리즘으로 풀어보겠습니다. (저는 그래프 관련 알고리즘 중에 다익스트라가 제일 재미있는것 같습니다🤮)

최단 경로가 아닌 거의 최단경로를 찾는 네비게이션을 만든다는 생각 자체가 참 재밌는 문제인 것 같습니다.

풀이에 들어가겠습니다.