글 읽기 - 계속 메모리 초과 문제가 나는데 잘 모르겠습니다.

aquarius456 6년 전 0

계속 메모리 초과 문제가 나서 다른 사람 코드 확인해 봤는데 제 코드랑 다를 게 별로 없는데 메모리 초과 문제가 계속 나네요.

도와주세요

푸는 방식은 바이너리 서치를 이용해서 bfs를 했습니다.

#pragma warning(disable : 4996)
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int, int>> vec[100001];
bool visited[100001];
int minW = 0x7fffffff, maxW = 0;
int result;
int from, to;
int n, m;
queue<int> q;
bool bfs(int w) {
	int s = from;
	fill_n(visited,100001,false);
	while (q.size()) q.pop();
	visited[s] = true;
	q.push(s);
	while (!q.empty()) {
		s = q.front();
		q.pop();
		if (s == to) return true;
		for (int i = 0; i < vec[s].size(); i++) {
			 pair<int, int> p = vec[s][i];
			 if (!visited[p.first] && w <= p.second)
			 {
				 q.push(p.first);
				 visited[p.first];
			 }
		}
	}
	return false;
}	
void binary_search() {
	int f = minW, t = maxW;
	int mid;
	result = 0;
	while (f <= t) {
		mid = (f + t) / 2;
		if (bfs(mid)) {
			result = mid;
			f = mid + 1;

		}
		else {
			t = mid - 1;
		}
	}
}
int main() {
	int v, u,w;

	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++) {
		scanf("%d %d %d", &v, &u, &w);
		vec[v].push_back(make_pair(u, w));
		vec[u].push_back(make_pair(v, w));
		if (maxW < w) maxW = w;
		if (minW > w) minW = w;
	}
	scanf("%d %d", &from, &to);
	binary_search();
	printf("%d\n", result);
	return 0;
}

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

문제

문제

출처

ICPC

계속 메모리 초과 문제가 나는데 잘 모르겠습니다.

aquarius456 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말