개발일지

개념 최단거리를 구하는 알고리즘이다. 최단거리 + 최단거리 = 최단거리라는 그리디한 개념으로 최단거리를 찾는다. => 간선의 가중치가 음수인게 존재하면 다익스트라를 사용할 수 없다. (최단거리 + 최단거리 = 최단거리라는 보장이 깨지기 때문에) 작동원리 1. 시작 노드를 우선순위 큐에 넣는다. 2. 우선순위 큐에서 POP을한다. 3. POP한 노드가 최단거리이면 해당 노드에서 갈 수 있는 노드중 거리를 갱신하는 노드를 우선순위 큐에 PUSH한다. 4. 2 ~ 3을 우선순위 큐가 EMPTY가 될 때까지 한복한다. 시간복잡도 O(ElogV) 문제 11779 최소비용 구하기 2 www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)..