[C++] 백준 1922번 네트워크 연결

www.acmicpc.net/problem/1922

1922번: 네트워크 연결

앞서 풀었던 최소 스패닝 트리 문제와 사실상 동일한 문제였다.

하지만 런타임에러로 고생을 했었는데

edge.resize(100001);

이부분에서 resize를 m+1로 하니 너무 작게 선언한 것이 문제가 되어 결국 런타임에러가 발생해서 이유를 찾는데 고생을 했다.

다음 부터 mst문제를 풀 때에는 STL의 크기에 대해서 잘 생각을 하고 구현을 해야겠다고 생각했다.

또한 프림 알고리즘을 푸는 것이외에 크루스칼 알고리즘으로 푸는 것에 대해서도 공부를 좀 해봐야겠다.

 

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

int n, m, sum;
int visit[10001];
vector<vector<pair<int, int>>> edge;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void prim(int v) {
	visit[v] = 1;
	for (auto u : edge[v]) {
		if (!visit[u.second]) {
			pq.push(u);
		}
	}

	while (!pq.empty()) {
		auto w = pq.top();
		pq.pop();
		if (!visit[w.second]) {
			sum += w.first;
			prim(w.second);
			return;
		}
	}
}

int main() {
	int a, b, c;
	cin >> n >> m;
	edge.resize(100001);
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		edge[a].push_back({ c,b });
		edge[b].push_back({ c,a });
	}
	prim(1);
	cout << sum;
	return 0;
}