[2585] 경비행기

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

2585번: 경비행기

두 점이 주어질때 필요한 연료를 계산할때,

(0, 0), (100, 0)같이 딱 떨어지는 경우를 고려하기 위해 적당히 작은 값을 빼놓고 10으로 나눈 몫을 취했다.

해당 부분을 구현하고 나면 남은것은 방문처리인데, 어떤 정점을 더 적은 횟수로 경유해서 온 경우만 방문하기 위해

int vst[n]; 형태로 선언하여 방문처리 해주었다.

---

 

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

typedef struct {

    int x, y;

} state;

bool operator==(const state& A, const state& B) {

    return (A.x == B.x) and (A.y == B.y);

}

constexpr state S = {0, 0}, E = {10000, 10000};

int n, k;

vector<state> v;

int getScore(const state& A, const state& B) {

    double dst;

    double dx = A.x - B.x, dy = A.y - B.y;

    dst = sqrt(dx * dx + dy * dy);

    dst -= (1e-9);

    int ret = 1 + (int)dst / 10;

    return ret;

}

bool f(int sz) {

    queue<pair<state, int>> q;

    q.push({S, 0});

    int i, vst[1003];

    for (i = 0; i < n; i++) vst[i] = INT_MAX;

    while (!q.empty()) {

        state cur = q.front().first;

        int cnt = q.front().second;

        q.pop();

        if (cnt > k) continue;

        if (int sc = getScore(cur, E); sc <= sz) return true;

        if (cnt == k) continue;

        for (i = 0; i < n; i++) {

            if (vst[i] <= 1 + cnt) continue;

            int sc = getScore(cur, v[i]);

            if (sz < sc) continue;

            vst[i] = 1 + cnt;

            q.push({v[i], cnt + 1});

        }

    }

    return false;

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    int i, ans = INT_MAX;

    cin >> n >> k;

    v.resize(n);

    for (i = 0; i < n; i++) cin >> v[i].x >> v[i].y;

    int l = 0, r = getScore(S, E);

    while (l <= r) {

        int mid = (l + r) / 2;

        bool ret = f(mid);

        if (ret == true) {

            r = mid - 1;

            ans = min(mid, ans);

        } else

            l = mid + 1;

    }

    cout << ans;

    return 0;

}

---