[백준 / BOJ] C++ 3803 Networking

3803번: Networking

 

문제

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

3803번: Networking

 

 

풀이

여러 테스트 케이스에 대해 MST를 구하는 문제다. 최소 스패닝 트리(MST)는 주어진 정점을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소가 되는 트리다. 프림 알고리즘으로 MST를 구현했고 data set이  공백으로 구분되는 것은 무시해도 된다. 

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>

int V, E;
vector<pii> graph[10001];

int prim() {
  priority_queue<pii> pq;
  vector<int> visited(V + 1, 0);
  visited[1] = 1;
  for (pii edge : graph[1])
    pq.push(edge);
  int cost = 0;
  while (!pq.empty()) {
    int weight = -pq.top().first;
    int node = pq.top().second;
    pq.pop();
    if (!visited[node]) {
      visited[node] = 1;
      cost += weight;
      for (pii next : graph[node])
        if (!visited[next.second])
          pq.push(next);
    }
  }
  return cost;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  while (1) {
    cin >> V;
    if (V == 0)
      break;
    cin >> E;
    for (int i = 1; i <= V; i++)
      graph[i].clear();
    while (E--) {
      int a, b, c;
      cin >> a >> b >> c;
      graph[a].push_back({-c, b});
      graph[b].push_back({-c, a});
    }
    cout << prim() << '\n';
  }
  return 0;
}