Contents

[백준]1922 네트워크 연결

Contents

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

풀이:

[백준]1197 최소 스패닝 트리 참고

코드:

사용언어 : c++

 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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> P;
int N, E, q, w, e, b[1002] = { 1,1 };
int main() {
	cin >> N >> E;
	vector<priority_queue<P, vector<P>, greater<P>>> a(N + 1);
    vector<int> v = { 1 };
	for (int i = 0; i < E; i++) {
		cin >> q >> w >> e;
		a[q].push({ e,w });
		a[w].push({ e,q });
	}
	P p;
	q = 0;
	while (1) {
		p = { 10002, 0 };
		for (int i : v)
			while (!a[i].empty())
				if (b[a[i].top().second])	a[i].pop();
				else if (p.first > a[i].top().first) p = a[i].top();
				else	break;
		if (p.first < 10002) {
			b[p.second]++;
			v.push_back(p.second);
			q += p.first;
		}
		else	break;
	}
	cout << q << endl;
}