[2585] 경비행기

https://www.acmicpc.net/problem/2585

문제 이해를 잘못해서.. 해결하는데 엄청난 시간이 걸렸습니다.

이 문제는 (0, 0)에서 입력 받은 K이하의 노드를 거쳐서  (10000, 10000)으로 이동할 때 드는 연료의 최대값의 최솟값을 구하는 문제입니다.

(0, 0)을 A라고 가정하고 (10000, 10000)을 D라고 가정했을 때, A - B(임의의 노드)로 가는 연료가 1000이고 B - C(임의의 노드)로 가는 연료가 100이라면

A - B구간에서 1000만큼 필요했으므로 답은 1000이 나와야합니다.

이것을 모든 노드에 대해서 실행해보면 됩니다.

이분탐색을 이용해서 해당 비용만을 이용해서 (0, 0)에서 (10000, 10000) 목적지로 이동할 수 있는지를 계속해서 실행하면 됩니다.(bfs로)

코드입니다.

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
vii pos;
bool visit[(int)1e3 + 2];
 
int d(pii a, pii b) {
    int x = b.first - a.first;
    int y = b.second - a.second;
 
    return (int)ceil(sqrt(x * x + y * y) / 10);
}
 
bool bfs(int max_cost, int n, int k) {
    memset(visit, 0, sizeof(visit));
 
    queue<pii> q;
    q.push(mp(0, 0)); // from, k
 
    while (!q.empty()) {
        int from = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (from == pos.size() - 1) {
            if (cnt <= k + 1) return 1;
            else return 0;
        }
 
        for (int i = 1; i < pos.size(); i++) {
            if (visit[i]) continue;
 
            if (d(pos[i], pos[from]) <= max_cost) {
                visit[i] = 1;
                q.push(mp(i, cnt + 1));
            }
        }
    }
    
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, k;
    cin >> n >> k;
 
    pos.push_back(mp(0, 0));
 
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
 
        pos.push_back(mp(a, b));
    }
 
    pos.push_back(mp(1e4, 1e4));
 
    int left = 1, right = d(mp(0, 0), mp(1e4, 1e4));
 
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (bfs(mid, n, k)) right = mid - 1;
        else left = mid + 1;
    }
 
    cout << left;
 
    return 0;
}