BOJ 1922번 네트워크 연결

BOJ : https://www.acmicpc.net/problem/1922

 

MST에 대한 개념을 묻는 문제

 

우선순위 큐를 이용한 프림알고리즘을 이용했습니다

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
typedef pair<int, int> pii;
vector<pii> v[1005];
bool visit[1005];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int N, M;
 
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ c,b });
        v[b].push_back({ c,a });
    }
 
    priority_queue<pii, vector<pii>, greater<pii> > q;
    visit[1] = true;
    for (int i = 0; i < v[1].size(); i++) q.push({ v[1][i].first, v[1][i].second });
    int cnt = N - 1;
    int ret = 0;
    while (cnt) {
        int w = q.top().first;
        int n = q.top().second;
        q.pop();
        if (visit[n]) continue;
        visit[n] = true;
        ret += w;
        cnt--;
        for (int i = 0; i < v[n].size(); i++) if (!visit[v[n][i].second]) q.push({ v[n][i].first, v[n][i].second });
    }
    cout << ret;
 
    return 0;
}