Prim Algorithm

백준 1197번 https://www.acmicpc.net/problem/1197

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

int V, E;
int a, b, c;
bool visited[10001];
vector<vector<pii>> graph;
priority_queue<pii, vector<pii>, greater<>> pq;
int answer = 0;

void prim(int i) {

	visited[i] = true;
	for (auto u : graph[i]) {
		if (!visited[u.second]) pq.push({u.first, u.second});
	}

	while (!pq.empty()) {
		auto temp = pq.top();
		pq.pop();
		if (!visited[temp.second]) {
			answer += temp.first;
			prim(temp.second);
			return;
		}
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> V >> E;
	graph.resize(V + 1);
	for (int i = 0; i < E; i++) {
		cin >> a >> b >> c;
		graph[a].push_back({ c, b });
		graph[b].push_back({ c, a });
	}

	prim(1);
	cout << answer << endl;

	return 0;
}

연습용