[2211번] 네트워크 복구

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 우선순위 큐 다익스트라 :: http://programbasic.tistory.com/546 

이 문제는 우선순위 큐를 이용한 다익스트라로 해결할 수 있다.

최소 스패닝 트리로 접근하게 된다면, 결국 here->there을 갱신할 수 있는 방법이 없기에 다익스트라로 접근하는 편이 좋다.

다익스트라와 똑같이 구상하고, parent 배열을 둔다.

이 배열은 dist가 갱신 될 때 마다 갱신되는데, here정점에서 there정점으로 갱신이 될 때 

parent[there] = here은 유일하다는 것을 이용하여 접근한다.

따라서 parent[]배열은 정점의 수 - 1만큼 쌓일 것이고, 그 이유는 최소 스패닝 트리에 의하면

만약 정점이 4개이면 간선이 3개이기 때문이다.

따라서 parent배열 또한 간선이 서로 어떻게 연결되어있는지 표시하기에 V-1개가 입력된다. 

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

#include <iostream> #include <cstdio> #include <vector> #include <queue> #include <functional>   #define INF 987654321   using namespace std;   typedef pair<int, int> pii;   vector<pii> vc[1001]; int dist[1001]; int parent[1001];   int main() {     int V,E;     scanf("%d %d", &V, &E);       for (int i = 0; i < E; i++)     {         int from, to, val;         scanf("%d %d %d", &from, &to, &val);           vc[from].push_back(pii(to, val));         vc[to].push_back(pii(from, val));     }       // 최단 거리 INF 초기화     fill(dist, dist + 1001, INF);       // 최소 힙     priority_queue<pii, vector<pii>, greater<pii>> pq;          // first :: 최단 거리, second :: 정점 위치     pq.push(pii(0,1));     // 시작 위치의 최단 거리는 0이다.     dist[1] = 0;       while (!pq.empty())     {         int here = pq.top().second;         int hereCost = pq.top().first;                  pq.pop();           // here까지 최단 거리가 hereCost보다 작다면 continue         if (dist[here] < hereCost)             continue;           for (int i = 0; i < vc[here].size(); i++)         {             int there = vc[here][i].first;             int thereCost = vc[here][i].second + hereCost;               // there까지 최단 거리가 thereCost보다 크다면 갱신             if (dist[there] > thereCost)             {                 dist[there] = thereCost;                   pq.push(pii(thereCost, there));                   // 갱신이 된다면 parent는 유일하다.                 parent[there] = here;             }         }     }       // 정점의 수 - 1이 회선 개수이다.      printf("%d\n", V - 1);       for (int i = 2; i <= V; i++)         printf("%d %d\n", parent[i], i);          return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus