백준 1922번 네트워크 연결 / MST(프림)

전형적인 MST 프림 문제

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

 

V는 최대 1,000인데 E는 최대 100,000이니까 E >= VlogV를 기준으로

즉 100,000 >= 1000 * 16.6이므로 크로스칼보단 프림이 유리하다.

 

근데 정작 프림으로 풀고나서 다른 사람들 제출한 기록 보니까 크루스칼로 푼 사람들이랑 비슷하거나 오히려 느렸다....

그냥 프림 한번 써봤다는 의의로 기록 남긴다.

 

하나 주의할 점은 입력할때 { from, to, cost }에 { 1, 2, 10 }은 들어오는데 { 2, 1, 10 }은 안들어와서 입력받을때 둘 다 내가 넣어줘야 한다는 점이다.

#include <bits/stdc++.h>
using namespace std;

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

	int N, M;
	cin >> N >> M;

	// line[1]에는 1과 인접한 간선들의 정보가 들어감
	// line[1][0] 은 1에 인접된 첫번째 간선의 정보이며 to, cost 순서인 pair객체
	vector<vector<pair<int, int>>> lines(N + 1); // 정점을 1번부터 쓰니까 N + 1
	int from, to, cost;
	for (int i = 0; i < M; i++) {
		cin >> from >> to >> cost;
		lines[from].push_back({ to, cost });
		lines[to].push_back({ from, cost }); // 반대로 가도 비용 같으니 넣어주기
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	vector<bool> selected(N + 1, false);

	selected[1] = true; // 시작점 무난하게 1번으로
	for (auto p : lines[1]) { // 1번에 연결된 정점들 정보 업데이트
		int adj_vertex = p.first;
		int distance_to_adj = p.second;
		pq.push({ distance_to_adj, adj_vertex }); // dist로 정렬하기 위해 순서 반대로
	}

	int answer = 0;
	while (pq.size()) {
		int distance_to_this = pq.top().first;
		int this_vertex = pq.top().second;
		pq.pop();
		
		if (selected[this_vertex]) continue;

		selected[this_vertex] = true; // 가장 가까운 곳 선택하고
		for (auto p : lines[this_vertex]) { // 이 정점에서의 거리 업데이트
			int adj_vertex = p.first;
			int distance_to_adj = p.second;
			if(!selected[adj_vertex]) pq.push({ distance_to_adj, adj_vertex });
		}

		answer += distance_to_this;		
	}

	cout << answer;

	return 0;
}