글 읽기 - 메모리 초과 질문 드립니다

rlarlgns012 7년 전 0

메모리 초과가 발생했는데... queue 가 터진걸까요?

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> graph;
queue<int> q;
int N, K, M;
int result = -1;

void process() {

	vector<bool> visited(graph.size(), false);
	vector<int> graph_cnt(graph.size(), 9999999);
	q.push(1);
	visited[1] = 1;
	graph_cnt[1] = 1;

	while (!q.empty()) {

		int tmp = q.front();
		q.pop();

		if (tmp == N) {
			result = graph_cnt[N];
			return;
		}

		for (int i = 0; i < graph[tmp].size(); i++) {
			int next = graph[tmp][i];
			if (visited[next] == 0) {

				visited[next] = 1;
				q.push(next);
				graph_cnt[next] = graph_cnt[tmp] + 1;
			}
			else if (graph_cnt[next] > graph_cnt[tmp] + 1) {

				graph_cnt[next] = graph_cnt[tmp] + 1;
			}
		}
	}
}

int main() {

	scanf("%d %d %d", &N, &K, &M);

	for (int i = 0; i <= N; i++) {
		vector<int> v;
		graph.push_back(v);
	}

	for (int i = 0; i < M; i++) {

		vector<int> tmp;
		for (int j = 0; j < K; j++) {
			
			int t;
			scanf("%d", &t);
			tmp.push_back(t);
		}
		for (int j = 0; j < tmp.size(); j++) {
			for (int k = j+1; k < tmp.size(); k++) {
				graph[tmp[j]].push_back(tmp[k]);
				graph[tmp[k]].push_back(tmp[j]);
			}
		}
		tmp.clear();
	}

	process();

	printf("%d\n", result);
	return 0;
}

nisroeld99 7년 전 1

만약에 모든 간선 연결해주면 1000^3 만큼 메모리 사용해서 메모리 오버됩니다

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

문제

문제

출처

ICPC

메모리 초과 질문 드립니다

rlarlgns012 7년 전 0

nisroeld99 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말