[백준/BOJ] 백준 1922번 : 네트워크 연결

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

1922번: 네트워크 연결

모든 컴퓨터를 연결하는데 필요한 최소 비용은 최소 스패닝 트리의 가중치이다. 프림 알고리즘을 이용하여 최소 스패닝 트리의 가중치를 구한다.

 

코드

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

int n, m;
vector<pair<int,int>> adj[1001]; //pair는 가중치, 연결정점 순

//모든 컴퓨터를 연결하는데 필요한 최소 비용은 최소 스패닝 트리의 가중치이다
//프림 알고리즘을 이용하여 최소 스패닝 트리의 가중치를 구한다
int Solve()
{
	int ret = 0;

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

	//1번 정점부터 시작
	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 >> n >> m;

	for (int i = 0; i < m; 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;
}