글 읽기 - 왜 메모리초과가 나는지 모르겠습니다ㅜㅠ

hssk1528 4년 전 0

처음에 다익스트라로 구현할 때

각 도시까지 소요되는 시간을 기준으로 우선순위 큐를 사용하여

해당 소요 비용에 따른 최소 소요시간을 업데이트 해나가는 방식으로 구현했습니다.

그런데 계속 메모리 초과가 뜹니다ㅜㅜ

다른 방식으로 구현하여 정답을 받긴했지만 이 방법이 왜 메모리 초과가 나는지 궁금합니다..

다른 분들 풀이를 찾아 봤을 때 저와 비슷하게 구현한 것들이 많던데

왜 저만 메모리 초과가 나는지 모르겠습니다ㅠ 도와주시면 감사하겠습니다..

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

using namespace std;

int n, m, k;  // 공항의 수, 지원비용, 총 티켓 수
vector<vector<int> > adj[101];  // 각 공항에서 갈 수있는 (도착공항 번호, 비용, 시간) 리스트
int time[101][10001];  // 각 공항까지 해당 비용만큼 소비했을 때 갈 수 있는 최소 소요 시간

const int INF = 1e9;

int travel(int start) {
	priority_queue<vector<int> > q;  // (소요시간, 공항 번호, 비용)
	q.push(vector<int>{0, start, 0});
	time[start][0] = 0;

	while (!q.empty()) {
		int t = -q.top()[0];
		int here = q.top()[1];
		int money = q.top()[2];
		q.pop();

		if (time[here][money] < t) continue;

		// 현재 위치가 도착 도시이면 종료
		if (here == n) return t;

		// 현재 공항에서 갈 수 있는 모든 공항 탐색
		for (int i = 0; i < adj[here].size(); i++) {
			vector<int> there = adj[here][i];

			// 비용을 넘어가면 이동 불가
			if (money + there[1] > m) continue;

			// 지금까지 구한 최소 소요시간보다 소요시간이 작으면 업데이트
			if (time[there[0]][money + there[1]] > t + there[2]) {
				time[there[0]][money + there[1]] = t + there[2];
				q.push(vector<int>{-t - there[2], there[0], money + there[1]});
			}
		}
	}

	return -1;  // 지원 비용으로 도착도시에 갈 수 없는 경우
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);

	int t;  // 테스트 케이스 수
	cin >> t;

	for (int test = 0; test < t; test++) {
		cin >> n >> m >> k;

		// adj 초기화
		for (int i = 1; i <= n; i++) adj[i].clear();

		for (int i = 0; i < k; i++) {
			int a, b, c, d;
			cin >> a >> b >> c >> d;

			adj[a].push_back(vector<int>{b, c, d});
		}

		// time 배열 초기화
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= m; j++) {
				time[i][j] = INF;
			}
		}

		int res = travel(1);

		if (res == -1) cout << "Poor KCM\n";
		else cout << res << "\n";

	}

	return 0;
}

kyunamk 4년 전 0

아래 부분에서 .. 일단 이미 queue 되어진 것이 있다 해도 다시 push 되므로 multi path가 되는 경우, 값을 떠나서 아주 많은 양이 push 될 수 있습니다..

if (time[there[0]][money + there[1]] > t + there[2]) {
time[there[0]][money + there[1]] = t + there[2];
q.push(vector{-t - there[2], there[0], money + there[1]});
}

there과 money가 이미 queue in 되어 있으며 더이상 push 하지 않는 logic을 구현하다면, memory over는 나지 않을 것 같습니다.

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

문제

문제

출처

ICPC

왜 메모리초과가 나는지 모르겠습니다ㅜㅠ

hssk1528 4년 전 0

kyunamk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말