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

다익스트라 알고리즘에서 다음번에 방문할 곳의 정보를 선형으로 O(N)만에 알아내는 대신 priority queue를 이용해 O(lgN)만에 알아낼 수 있습니다. 이렇게 되면 시간복잡도가 O(E+V^2)에서 O((E+V)lgV)로 감소시킬 수 있습니다. E가 V^2에 수렴한다면 큰 차이는 없지만, 이 문제와 같이 E가 V^2보다 많이 작은 상황이라면 priority queue를 사용하는 것이 효율적입니다.

https://github.com/blisstoner/BOJ/blob/master/1753.cpp