[백준/BOJ] 백준 1197번 : 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

프림 알고리즘을 이용하여 최소 스패닝 트리의 가중치를 구한다

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int v, e;
vector<pair<int,int>> adj[10001]; //pair는 가중치, 연결정점 순

//프림 알고리즘을 이용하여 최소 스패닝 트리의 가중치를 구한다
int Solve()
{
	int ret = 0;

	vector<int> selected(v + 1, 0); //해당 정점이 최소 스패닝 트리에 연결이 되었는지 확인
	priority_queue<pair<int, int>> pq; //pair는 정점으로 오는 가중치, 정점 순으로 저장

	pq.push(make_pair(-0, 1));

	while (!pq.empty())
	{
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();

		//현재 정점이 이미 최소 스패닝 트리에 연결 되어 있을때
		if (selected[here] == 1)
			continue;

		selected[here] = 1;//현재 정점을 최소 스패닝 트리에 연결한다
		ret += cost;//현재 정점으로 오는 가중치 저장

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there_cost = adj[here][i].first;
			int there = adj[here][i].second;

			//현재 정점과 연결된 there정점이 이미 최소 스패닝 트리에 연결 되었을때
			if (selected[there] == 1)
				continue;

			pq.push(make_pair(-there_cost,  there));
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int a, b, c;

	cin >> v >> e;

	for (int i = 0; i < e; i++)
	{
		cin >> a >> b >> c;
		adj[a].push_back(make_pair(c, b));
		adj[b].push_back(make_pair(c, a));
	}

	cout << Solve();


	return 0;
}