백준2585 경비행기

작성일 | In

문제 링크

  • http://icpc.me/2585

문제 출처

  • 2005 KOI 고등부 2번

사용 알고리즘

  • 파라메트릭 서치
  • BFS

시간복잡도

  • $O(N^2 \log X)$

풀이

연료통의 크기가 $X$일 때 $S$에서 $T$까지 중간급유를 $K$번 이하로 해서 갈 수 있는지 판별할 수 있다면 파라메트릭 서치로 문제를 해결할 수 있습니다.

길이가 $X$ 이하인 간선을 $K+1$개 사용해서 $T$에 도달할 수 있는지 판별하면 되고, BFS를 통해 쉽게 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n, k; p a[1010];
vector<int> g[1010];
int vst[1010];

ll dst(p s, p e){
    ll dx = s.x - e.x, dy = s.y - e.y;
    return dx*dx + dy*dy;
}

int chk(ll x){
    ll lim = 100LL * x * x;
    for(int i=1; i<=n; i++) g[i].clear();
    for(int i=1; i<=n; i++) for(int j=1; j<i; j++){
        if(dst(a[i], a[j]) <= lim){
            g[i].push_back(j); g[j].push_back(i);
        }
    }
    memset(vst, -1, sizeof vst);
    queue<int> q; q.push(1); vst[1] = 0;
    while(q.size()){
        int v = q.front(); q.pop();
        for(auto i : g[v]) if(vst[i] == -1) {
            vst[i] = vst[v] + 1; q.push(i);
        }
    }
    return vst[n] <= k+1 && vst[n] != -1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k; n += 2; for(int i=2; i<=n-1; i++) cin >> a[i].x >> a[i].y;
    a[1] = p(0, 0); a[n] = p(10000, 10000);
    int l = 0, r = 20202;
    while(l < r){
        int m = l + r >> 1;
        if(chk(m)) r = m;
        else l = m + 1;
    }
    cout << r;
}