글 읽기 - c++ 반례를 찾아주세요

dummy20logroot2 2년 전 0

순간이동 비용이 0이므로 어떤 지점을 큐에 넣을 때 순간이동 가능한 위치도 모두 함께 넣어서 큐 내부 정렬이 유지되게 했습니다. 어느 부분이 문제인지 알 수 있을까요?

#include<iostream>
#include<queue>
using namespace std;

//너비 우선 탐색을 위한 큐 선언
queue<int>q;
int dp[100001];
int N,K;
void BFS(){
	int t;
	while(!q.empty()){
		//맨 앞의 큐 값을 받아온다
		t=q.front();
		q.pop();

		for(int i:{t+1, t-1, t*2}){
			for(int j=i; j!=0; j*=2){
				if(0>j || j>100000)break;
				if(dp[j]==-1){
					q.push(j);
					dp[j]=dp[t]+1;
				}
			}
		}
	}//return -4;
}

int main(){
	fill(dp, dp+100001, -1);
	cin>>N>>K;

	q.push(0);
	dp[0]=0;
	for(int j=N; j!=0; j*=2){
		if(0>j || j>100000)break;
		if(dp[j]==-1){
			q.push(j);
			dp[j]=0;
		}
	}
	BFS();
	cout<<dp[K];
}

dummy20logroot2 2년 전 1

0으로 가는 경우를 아예 배제해서 문제가 있었네요

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

문제

문제

출처

ICPC

c++ 반례를 찾아주세요

dummy20logroot2 2년 전 0

dummy20logroot2 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말