글 읽기 - 프림이 빠른가요 크루스칼이 빠른가요(C++)

junsik456 2년 전 0

저는 프림으로 구현하였습니다. 1600ms 정도가 나왔어요.

근데다른분들보니까 400~500ms정도 나왔더라구요.

이 문제에 프림알고리즘이 적합하지 않은것인지 제가 짠코드에 더 시간을 많이잡아먹는 부분이 어떤것인지 알고싶습니다 .ㅜ

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class cmp
{
public:
	bool operator()(const pair<int, int> a,const pair<int, int> b)
	{
		return a.second > b.second;
	}
};

vector<pair<int, int>> v[100001];
int main(void)
{
	int N, M;
	cin >> N >> M;
	int a, b, c;
	//v[i]번째 정점에 연결된 값을 pair<정점,가중치>데이터로 받아들임
	while (M--)
	{
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
		v[b].push_back(make_pair(a, c));
	}
	
	priority_queue <pair<int, int>, vector<pair<int, int>>, cmp> pq;
	priority_queue<int> sum;
	int visited[100001] = { 0 };

	//임의의 정점 a 로 시작
	//간선이 N-1개 일 때 종료

	for (int V = a, cnt = 0; cnt != N-1;)
	{
		//방문처리
		visited[V] = 1;
		//선택한 정점과 연결된 다른 정점과 그 가중치를 우선순위큐에 삽입
		for (int i = 0; i < v[V].size(); i++)
		{
			pq.push(v[V][i]);
		}

		
		while (!pq.empty())
		{
			//이미 방문처리된 정점이라면 뽑고 다시시작
			if (visited[pq.top().first] == 1)
			{
				pq.pop();
				
				continue;
			}
			//방문처리 안된거면 정점의 값을 V에저장하고
			V = pq.top().first;
			//가중치값을 sum 큐에 넣어준다
			sum.push(pq.top().second);
			pq.pop();
			cnt++;
			
			break;
		}
		
	}
	//마을을 나눌때 가중치가 가장큰 도로를 부심
	sum.pop();
	int road = 0;
	//나머지 합
	while (!sum.empty())
	{
		road += sum.top();
		sum.pop();
	}
	cout << road;

	return 0;
}

qhsl1213 2년 전 0

원래 크루스칼이 좀 더 빠른걸로 알고있습니다.

shjohw12 2년 전 1

둘다빠릅니다

ios::sync_with_stdio(0); cin.tie(0);

이거안해줘서 느린것같네요

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

문제

문제

출처

ICPC

프림이 빠른가요 크루스칼이 빠른가요(C++)

junsik456 2년 전 0

qhsl1213 2년 전 0

shjohw12 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말