백준 16398번 행성 연결 / MST(프림)

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

 

이 문제도 전형적인 MST문제이다.

V는 1 ~ 1000인데 E가 V * V라서 프림을 선택하고 풀어봤다.

근데 이번에도 역시 크루스칼이랑 속도 차이가 없다... 진짜 간선이 어마어마하게 많아야만 의미가 있는건가 싶다.

 

아무튼 이 문제의 차별점은 입력이 인접리스트가 아니라 인접 배열이라는 점이다.

그 외엔 그냥 프림문제다.

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

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

	int N;
	cin >> N;

	vector<vector<int>> costs(N, vector<int>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> costs[i][j];
		}
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

	vector<bool> selected(N, false);
	selected[0] = true;
	for (int i = 1; i < costs[0].size(); i++) {
		int adj_vertex = i;
		int distance_to_adj = costs[0][i];
		pq.push({ distance_to_adj, adj_vertex });
	}

	long long 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 (int i = 0; i < costs[this_vertex].size(); i++) {
			if (this_vertex == i) continue;

			int adj_vertex = i;
			int distance_to_adj = costs[this_vertex][i];
			if (!selected[adj_vertex]) pq.push({ distance_to_adj, adj_vertex });
		}

		answer += distance_to_this;
	}

	cout << answer;

	return 0;
}