글 읽기 - 맞았습니다 가 나오지만 메모리를 많이 잡아먹고 시간이 오래걸려요

suic97 4년 전 0

ㅇㅓ디서 오래걸리는 걸까요...? 어떻게 고쳐야 좀 더 빠르게 돌아갈수 있을까요ㅠㅡㅠ 메모리는 왜이렇게 많이 잡아먹나요?

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

#define MAX 100001
using namespace std;
vector<pair<int, int> > prim_v[MAX];

bool is_visited[MAX];
priority_queue < pair<int, int>, vector < pair<int, int> >, greater<pair<int, int>> > pq;

int vertex = 0;
int prim(int start_v) {

	int ans = 0;
	int large_weight = 0;

	pq.push(make_pair(0, start_v));

	while (!pq.empty()) {
		int weight = pq.top().first; int v = pq.top().second;
		pq.pop();

		if (is_visited[v]) continue;

		is_visited[v] = true;
		ans += weight;
		vertex--;
		
		if (large_weight < weight) large_weight = weight;
		
		if (vertex == 0) break;

		for (int i = 0; i < prim_v[v].size(); i++) {
			int weight = prim_v[v][i].first;
			int next_vertex = prim_v[v][i].second;

			if (is_visited[next_vertex]) continue;
			pq.push(make_pair(weight, next_vertex));
		}
	}

	cout << ans - large_weight << endl;
	return ans;
}
int main() {
	int n, m;
	int start_v = 1;
	cin >> n >> m;
	vertex = n;

	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		prim_v[u].push_back(make_pair(w, v));
		prim_v[v].push_back(make_pair(w, u));
	}
	prim(start_v);
}

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

문제

문제

출처

ICPC

맞았습니다 가 나오지만 메모리를 많이 잡아먹고 시간이 오래걸려요

suic97 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말