글 읽기 - 경비행기문제 이런식으로 하면 왜 안되는지에 대해서 알고 싶습니다.

icantgiveup 2년 전 0

반례를 알고 싶습니다.

현재 위치에서 연료로 갈 수 있는 거리에 있는 경유지를 큐에 넣는 방식으로 풀었는데, 왜 틀린지에 대해서 알고 싶습니다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int n, k;
vector <pair<int, int>> vec;
bool visited[1001];

bool bfs(int g) {
	queue <pair<int, pair<int, int>>> q;
	q.push({ 0, {0,0} });
	visited[0] = 1;
	while (!q.empty()) {
		auto current = q.front();
		if (current.second.first == 10000 && current.second.second == 10000) {
			if (current.first <= k + 1) {
				return 1;
			}
			else {
				return 0;
			}
		}
		q.pop();
		for (int i = 0; i < vec.size(); i++) {
			int far = pow(vec[i].first - current.second.first, 2) + pow(vec[i].second - current.second.second, 2);
			if (far <= pow(g, 2) && !visited[i]) {
				visited[i] = 1;
				q.push({ current.first + 1, {vec[i].first,vec[i].second} });
			}
		}
	}
	return 0;
}

int main(void) {
	fastio;

	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		vec.push_back({ x,y });
	}
	vec.push_back({ 0,0 });
	vec.push_back({ 10000,10000 });

	sort(vec.begin(), vec.end());

	int low = 1;
	int high = 1415;
	int result = 0;

	while (low <= high) {
		int mid = (low + high) / 2;

		if (bfs(mid * 10)) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
		memset(visited, 0, sizeof(visited));
	}
	cout << low;

	return 0;
}

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

문제

문제

출처

ICPC

경비행기문제 이런식으로 하면 왜 안되는지에 대해서 알고 싶습니다.

icantgiveup 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말