문제

입력 출력 예시

해결 방법

이 문제는

1. 간선에 가중치가 있으며
2. 가중치가 모두 양수일 때
3. 특정 두 정점을 지나는 최단 거리를 구하고
4. 최단 경로가 없으면 -1 출력

따라서 간선 가중치가 양수이면서 한 점에서 다른 점까지의 최단 거리를 구하는 다익스트라 알고리즘을 사용하여 풀 수 있다.

최단 거리 알고리즘 중 다익스트라 선택 이유