글 읽기 - 메모리 초과에 관해

seokjw96 3년 전 0

최대한 메모리 줄인건데... 왜 메모리 초과가 발생하는지 원인을 모르겠습니다. 정말 이것때문에 미치겠네요...알려주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAX 501
#define endl "\n"
using namespace std;
typedef pair<int, int> pii;
int adj[MAX][MAX];
vector<int> trace[MAX];
int n, m, s, d;
const int INF = 987654321;
int dist[MAX];
int u, v, p;

void dijkstra() {
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for (int i = 0; i < n; i++) {
		dist[i] = INF;
	}
	dist[s] = 0;
	pq.push({ dist[s],s });
	while (!pq.empty()) {
		int cost = pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (dist[cur] < cost)continue;
		for (int i = 0; i < n; i++) {
			if (adj[cur][i] == 0)continue;
			int nCost = cost + adj[cur][i];
			if (dist[i] > nCost) {
				dist[i] = nCost;
				pq.push({ dist[i],i });
				trace[i].clear();
				trace[i].push_back(cur);
			}
			else if (dist[i] == nCost) {
				trace[i].push_back(cur);
			}
		}
	}
}

void deleteLink() {
	queue<int> q;
	q.push(d);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < trace[cur].size(); i++) {
			adj[trace[cur][i]][cur] = 0;
			q.push(trace[cur][i]);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0)break;
		cin >> s >> d;
		memset(adj, 0, sizeof(adj));
		for (int i = 0; i < n; i++) {
			trace[i].clear();
		}
		for (int i = 0; i < m; i++) {
			cin >> u >> v >> p;
			adj[u][v] = p;
		}
		dijkstra();
		deleteLink();
		dijkstra();
		if (dist[d] == INF)cout << -1 << endl;
		else cout << dist[d] << endl;
	}
	return 0;
}

asdsa2134 3년 전 0

delteLink부분을 bfs말고 dfs로 풀어보시면 메모리초과 피하실수 있으실거예요

seokjw96 3년 전 0

감사합니다 해결은 했는데, 이 문제 자체가 bfs 사용시 큐에 할당되는 메모리를 사용하면 메모리초과가 날 것이라고 생각하지 못했네요... n은 상대적으로 적은 반면 간선의 갯수가 상당히 많아서 그런걸까요?

asdsa2134 3년 전 1

네 최단경로 중에서 겹치는 노드들을 제거하면 더 적은 메모리로도 가능할 것 같아요

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

문제

문제

출처

ICPC

메모리 초과에 관해

seokjw96 3년 전 0

asdsa2134 3년 전 0

seokjw96 3년 전 0

asdsa2134 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말