글 읽기 - 프림으로 풀었을경우 시간이 매우많이걸리는 이유가 뭘까요?

spring2 3년 전 0

프림과 크루스칼 시간이 비슷한걸루 알고있는데

크루스칼이 프림보다 더 빠른 알고리즘인건가요 아니면 제 프림 소스가 이상한건가요 ㅜㅜ..

맞았습니다 뜨긴하였으나 시간이 매우아슬아슬한걸 보아 불안합니다 뭔가 문제가 있는것 같은데 뭘까요 ㅜㅜ

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool check[100001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int,int>>>v(n + 1);
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back(make_pair(y, z));
		v[y].push_back(make_pair(x, z));
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
	q.push(make_pair(0,1));
	int maxcost = -1;
	int ans = 0;
	while (!q.empty()) {
		int fd = q.top().first;
		int fx = q.top().second;
		q.pop();
		if (check[fx])	continue;
		check[fx] = true;
		if (maxcost < fd)	maxcost = fd;
		ans += fd;
		for (int k = 0; k < v[fx].size(); k++) {
			int nx = v[fx][k].first;
			int cost = v[fx][k].second;
			q.push(make_pair(cost, nx));			
		}
	}
	ans -= maxcost;
	cout << ans << '\n';
	return 0;
}

rpfdjq3 2년 전 0

prim 알고리즘은 edge를 선택하는 매 순간 최적의 선택을 하는 것으로 총 N-1개의 edge를 선택하는 순간 종료해도 무관합니다. 위 코드는 queue가 empty가 될때까지 돌아가고 36번째줄에 이미 방문한 노드도 queue에 추가하기 때문에 오래걸리는거 같네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

프림으로 풀었을경우 시간이 매우많이걸리는 이유가 뭘까요?

spring2 3년 전 0

rpfdjq3 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말