[백준] 16398 행성연결 - MST, 우선순위 큐

[ 문제링크 ]

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

 

 

🚩 조건

1. 제국 내 모든 행성을 연결
2. 그 유지비용을 최소화

 

🚩 접근

1,2 -> 최소신장트리 => Prim 알고리즘을 이용하자!

 

🚩 시행착오

플로우 관리 비용의 범위가 "1 ≤ Cij ≤ 100,000,000"이므로, 처음에 ans를 int로 선언하여 "틀렸습니다"가 나옴
=> ans를 long long으로 선언하여야 함

 

 

💻 코드 (C++)

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

priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq; //cost, a, b
vector<pair<int, int>> adj[1001]; //cost, b
bool check[1001];
int main() {
	int N, c;
	int a, b;
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> c;
			if (c == 0)continue;
			adj[i].push_back({ c,j });
		}
	}

	//첫 방문 : 0번 행성
	int cnt = 1;
	long long ans = 0;
	a = 0; check[a] = true;

	while (cnt <= N - 1) {
		for (auto next : adj[a]) {
			pq.push({ next.first, a, next.second });
		}
		tie(c, a, b) = pq.top();
		while (check[b]) {
			pq.pop();
			tie(c, a, b) = pq.top();
		}
		ans += c;
		check[b] = true;
		a = b;
		pq.pop();
		cnt++;
	}

	cout << ans;
}