글 읽기 - 메모리 초과가 어느 부분에서 날까요.. ㅠㅠ

gktgnjftm 5년 전 0

a는 그래프를 표현하기 위하여 resize를 정점갯수+1개, 그냥 넉넉하게 했고, dist배열과 path배열 earn배열의 사이즈는 105개 밖에 안됩니다. 그냥 고민인게 혹시 사이클의 정점을 추적하기 위한 path배열쪽과 spot 벡터가 문제일수 있다고 생각을 합니다. 근데 메모리초과가 정말 어디서 나는지 도저히 모르겠습니다. ㅠㅠㅠ

고수님들 죄송하지만 메모리초과 한번 잡아주시면 감사하겠습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n, start, en, m;
typedef long long ll;
typedef pair<int, ll> P;
vector<vector<P>> a;
ll earn[105];
ll dist[105];
int path[105];
#define INF 100000000000
ll lastvisit;
vector<int> spot;
bool visited[105];
queue <int> q;
bool ok;
void bfs(){
	for (int i = 0; i < spot.size(); i++) {
		q.push(spot[i]);
	}
	while (!q.empty()) {
		int here = q.front();
		q.pop();
		visited[here] = true;
		if (here == en) {
			ok = true;
			break;
		}
		for (int i = 0; i < a[here].size(); i++) {
			int next = a[here][i].first;
			if (!visited[next]){
				q.push(next);
			}
		}
	}
}
void go(ll here) {
	if (here == lastvisit) return;
	else {
		go(path[here]);
		spot.push_back(here);
	}
}
int main(){
	scanf("%d%d%d%d", &n, &start, &en, &m);
	a.resize(n + 1);
	for (int i = 1; i <= m; i++) {
		int first, second;
		ll cost;
		scanf("%d%d%lld", &first, &second, &cost);
		a[first].push_back({ second,cost });
	}
	for (int i = 0; i < n; i++) {
		scanf("%lld", &earn[i]);
	}
	for (int i = 0; i < n; i++) {
		dist[i] = INF;
	}
	bool cyclecheck = false;
	dist[start] =-earn[start];
	lastvisit = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < a[j].size(); k++) {
				int next = a[j][k].first;
				ll nextcost = a[j][k].second;
				if (dist[j] != INF && dist[next] > dist[j] + nextcost-earn[next]) {
					dist[next] = dist[j] + nextcost-earn[next];
					if (i == n - 1) {
						cyclecheck = true;
						path[next] = j;
						lastvisit = next;
					}

				}
			}
		}
	}
	if (!cyclecheck) { 
		if (dist[en] != INF) {
			printf("%lld\n", -dist[en]);
		}
		else printf("gg\n");
	}
	else{
		go(path[lastvisit]);
		spot.push_back(lastvisit);
		bfs();
		if (dist[en] == INF) printf("gg\n");
		else if (!ok) printf("%lld\n",-dist[en]);
		else if(ok)printf("Gee\n");
	}
	return 0;
}

gktgnjftm 5년 전 0

사이클 추적 DFS 부분에서 문제가 발생하였습니다. 어떤 테스트케이스로 인해서 메모리초과인지는 잘 모르겠으나, 사이클을 추적하는데 있어서 뭔가 문제가 발생하여서 제대로 되지 않아서 터진것 같습니당

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

문제

문제

출처

ICPC

메모리 초과가 어느 부분에서 날까요.. ㅠㅠ

gktgnjftm 5년 전 0

gktgnjftm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말