글 읽기 - 메모리 초과가 나는 이유가 뭘까요?

solo5star 3년 전 0

33%에서 계속 메모리 초과가 뜹니다. 소스코드를 아무리 봐도 메모리가 누수되거나 낭비되는 부분은 없는 것 같은데... 대체 어떤게 문제일까요?

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

typedef struct {
	int to;
	int cost;
} edge;

bool operator<(const edge& a, const edge& b) {
	return a.cost > b.cost;
}

int nodeCount;

int getShortestPath(vector<vector<edge>>& nodes, vector<vector<int>>& traces, int from, int to) {
	vector<int> costs(nodeCount, INT_MAX);
	priority_queue<edge> pq;

	pq.push({ from, 0 });
	costs[from] = 0;

	while (!pq.empty()) {
		edge e = pq.top();
		pq.pop();

		int mid = e.to;

		for (edge& _e : nodes[e.to]) {
			// removed
			if (_e.to == -1) continue;

			edge next = { _e.to, e.cost + _e.cost };

			if (costs[next.to] < next.cost) continue;

			if (costs[next.to] == next.cost) {
				traces[next.to].push_back(mid);
			}
			else {
				traces[next.to].clear();
				traces[next.to].push_back(mid);
			}

			costs[next.to] = next.cost;

			pq.push(next);
		}
	}

	return costs[to];
}

void removeShortestPath(vector<vector<edge>>& nodes, vector<vector<int>>& traces, int from, int to) {
	queue<int> midpoints;

	midpoints.push(to);

	while (!midpoints.empty()) {
		int _to = midpoints.front();
		midpoints.pop();

		for (int mid : traces[_to]) {
			// remove path
			for (int i = 0; i < nodes[mid].size(); i++) {
				if (nodes[mid][i].to == _to) nodes[mid][i].to = -1;
			}

			if (mid != from) midpoints.push(mid);
		}
	}
}

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

	//freopen("1.in", "r", stdin);

	int edgeCount;

	int from, to;
	int _from, _to, cost;

	while (true) {
		cin >> nodeCount >> edgeCount;

		if (nodeCount == 0 && edgeCount == 0) break;

		vector<vector<edge>> nodes(nodeCount);
		vector<vector<int>> traces(nodeCount);

		cin >> from >> to;

		for (int i = 0; i < edgeCount; i++) {
			cin >> _from >> _to >> cost;

			nodes[_from].push_back({ _to, cost });
		}

		getShortestPath(nodes, traces, from, to);

		removeShortestPath(nodes, traces, from, to);

		cost = getShortestPath(nodes, traces, from, to);

		cout << (cost == INT_MAX ? -1 : cost) << "\n";
	}
}

solo5star 3년 전 0

사실상 시간 초과되는 코드였고 priority_queue에 다음 간선을 추가할 때 같은 비용들의 간선을 모두 추가하여 메모리 및 시간 초과가 났습니다. 아래와 같이 코드 수정하여 해결하였습니다.

if (costs[next.to] == next.cost) {
    traces[next.to].push_back(mid);
}
else {
    traces[next.to].clear();
    traces[next.to].push_back(mid);
                
    pq.push(next);
}

costs[next.to] = next.cost;

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

문제

문제

출처

ICPC

메모리 초과가 나는 이유가 뭘까요?

solo5star 3년 전 0

solo5star 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말