글 읽기 - 메모리 초과 이유를 알고싶습니다.

kravi 3년 전 0

재채점하고 나서 메모리 초과가 발생했는데

처음엔 중복으로 들어오는 노선들이 많아서 우선순위 큐가 터지나 싶어서

인접행렬로 변경하고 값을 걸러받았는데도 메모리가 터지네요

도움 부탁드립니다.

#include <bits/stdc++.h>
using namespace std;
// 11779 최소비용 구하기 2
#define FOR(i, n, m) for(int i=(n); i<(m); i++)
#define cost first
#define vert second
using PII = pair<int, int>;
constexpr int INF = 100000002;
constexpr int VLIM = 1002;

// vector<PII> adj[VLIM];
int adj[VLIM][VLIM];
priority_queue<PII, vector<PII>, greater<PII>> pQ;
int minCost[VLIM];
int route[VLIM];
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int V, E, F, T;
	cin >> V >> E;
	FOR(i, 0, V + 1) fill(adj[i], adj[i] + V + 1, INF);
	FOR(i, 0, E) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a][b] = min(adj[a][b], c);
	}
	cin >> F >> T;
	fill(minCost, minCost + V + 1, INF);
	minCost[F] = 0;
	pQ.push({ 0, F });
	while (!pQ.empty()) {
		int vv, vc;
		tie(vc, vv) = pQ.top(); pQ.pop();
		if (vc != minCost[vv]) continue;
		FOR(nv, 0, V+1) {
			if (adj[vv][nv] == INF) continue;
			int nc = vc + adj[vv][nv];
			if (minCost[nv] < nc) continue;
			minCost[nv] = nc;
			route[nv] = vv;
			pQ.push({ nc, nv });
		}
	}
	cout << minCost[T] << '\n';
	vector<int> enRoute = { T };
	while (enRoute.back() != F) {
		enRoute.push_back(route[enRoute.back()]);
	}
	cout << enRoute.size() << '\n';
	for (auto i = enRoute.rbegin(); i != enRoute.rend(); i++) {
		cout << *i << ' ';
	}
}

djm03178 3년 전 4

39번째 줄의 부등호를 <=로 바꾸면 맞습니다. 모든 간선이 0으로 주어질 때의 동작을 생각해 보세요.

kravi 3년 전 0

@djm03178

세상에... 큰 깨달음 얻고갑니다 감사합니다

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

문제

문제

출처

ICPC

메모리 초과 이유를 알고싶습니다.

kravi 3년 전 0

djm03178 3년 전 4

kravi 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말