1916 최소비용 구하기

벨만포드 알고리즘은 O(VE)의 시간이 걸리므로 절대로 0.5초에 해결할 수 없다

다만, 다익스트라 알고리즘으로 모든 정점에 대해서 한 번씩 검사하고, 검사할 정점을 찾는데 정점의 개수만큼 시간이 걸리기 때문에 O(V^2)으로 문제를 해결할 수 있다

 

문제: https://www.acmicpc.net/problem/1916

소스코드: https://github.com/surinoel/boj/blob/master/1916.cpp

우선순위큐 소스코드: https://github.com/surinoel/boj/blob/master/1916_pq.cpp