글 읽기 - 2887 행성터널 프림알고리즘 메모리초과

hyj5419 5년 전 0

프림알고리즘으로 풀었는데 메모리초과가 나네요 ㅠㅠ 큐에 들어가는 것을 적게 해볼려고 제일 작은 값만 큐에 넣으면 시간초과가 뜹니다.

프림알고리즘으로 어떻게 풀어야하는지 도와주세요 ㅠㅠ

감사합니다.

#include<iostream>
#include<stdio.h>
#include<utility>
#include<vector>
#include<algorithm>
#include<stack>
#include<string.h>
#include<queue>
#include<set>
#include<ostream>
#include<map>
#include<string>
#include<deque>

using namespace std;
vector < pair<int, pair<int, int > >> w;
priority_queue<pair<int,int> > pq;
int visit[100005];
int INF = 9999999;
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		w.push_back({ x,{y,z} });

	}
	pq.push({ 0,1 });
	int sum = 0;
	while (!pq.empty()) {
		int now = pq.top().second;
		//printf("node : %d , weight : %d\n", pq.top().second,-pq.top().first);
		int temp = -pq.top().first;
		pq.pop();
		if (visit[now] == 1) continue;
		sum += temp;
		visit[now] = 1;
		int nx = w[now - 1].first;
		int ny = w[now - 1].second.first;
		int nz = w[now - 1].second.second;
		for (int i = 1; i <= n; i++) {
			int bx = w[i - 1].first;
			int by = w[i - 1].second.first;
			int bz = w[i - 1].second.second;
			int temp = min(abs(nx - bx), abs(ny - by));
			int weight = min(temp, abs(nz - bz));
			pq.push({ -weight,i });
		}
	}
	printf("%d\n", sum);
}

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

문제

문제

출처

ICPC

2887 행성터널 프림알고리즘 메모리초과

hyj5419 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말