글 읽기 - 도움 부탁드립니다. 시간초과가 뜹니다.

eodrnx2 6년 전 0

안녕하세요.

시간초과를 도저히 해결하지 못해 질문드립니다.

약 40% 조금 넘은 지점에서 시간초과에 걸립니다.

잘못된 점이 있다면 지적 부탁드립니다.

#include <iostream>
#include <queue>
using namespace std;
bool chk[1000001];
const int limit = 1000001;
int main(){
	int F, S, G, U, D;
	cin >> F >> S >> G >> U >> D;
	if (S < G && U == 0) {
		cout << "use the stairs" << endl;
		return 0;
	}
	if (S > G && D == 0) {
		cout << "use the stairs" << endl;
		return 0;
	}
	if (S < G && S + U > limit){
		cout << "use the stairs" << endl;
		return 0;
	}
	if (S > G && S - D < 1){
		cout << "use the stairs" << endl;
		return 0;
	}
	if (S < G && G - S < U && D == 0){
		cout << "use the stairs" << endl;
		return 0;
	}
	if (S > G && S - G < D && U == 0){
		cout << "use the stairs" << endl;
		return 0;
	}

	pair <int, int> odo;
	queue <pair<int, int>> q;
	q.push(make_pair(S, 0));
	int now, next, count;
	while (!q.empty()){
		odo = q.front();
		q.pop();
		now = odo.first;
		count = odo.second;
		chk[now] = true;
		if (now == G) {
			cout << count << endl;
			return 0;
		}
		count = odo.second + 1;
		next = odo.first + U;
		if ((!chk[next]) && next <= limit) q.push(make_pair(next, count));
		next = odo.first - D;
		if ((!chk[next]) && next > 0) q.push(make_pair(next, count));
	}
	cout << "use the stairs" << endl;
	return 0;
}

djm03178 6년 전 2

BFS는 큐에 넣는 순간에 방문 체크를 해야 중복 방문이 일어나지 않습니다. 큐에서 뺀 다음에 하려면 이미 늦습니다.

eodrnx2 6년 전 0

감사합니다.

성공적으로 해결되었습니다.

생각하지도 못한 곳에 원인이 있었네요..

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

문제

문제

출처

ICPC

도움 부탁드립니다. 시간초과가 뜹니다.

eodrnx2 6년 전 0

djm03178 6년 전 2

eodrnx2 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말