[1686] 복날

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

흠흠...

사실 최단 거리라기 보다는.. 가장 비용을 적게 들여서(가장 벙커를 적게 방문하면서) 목적지로 도달하는 문제입니다.

처음에 접근은 이분탐색으로 했습니다.

벙커들을 sort하여 갈 수 있는 시간내로 이동할 수 있는 최대 거리로 이동을 하여서 목적지에 도달하게 했습니다.

이 문제에서 이분탐색을 쓰면 생기는 오류는 방향입니다.

x, y 좌표가 있기 때문에 방향이 있어서 최대한의 거리가 절대값이기 때문에 오류가 발생합니다.

그래서 dfs로 해결하려 했으나 dfs는 최적의 해를 보장해주지 않기 때문에 완전 탐색을 해야만합니다.

시간초과로 실패했습니다.

해결 방법은 bfs 혹은 다익스트라로 해결하시면 됩니다.

사실 해보니깐.. 다익스트라는 딱히 필요없는듯.. 어차피 bfs는 최적을 보장하기 때문에.......

풀 코드입니당.

#include <cstdio>
#include <queue>
 
using namespace std;
 
#define mp make_pair
#define ll long long
 
vector<pair<double, double> > b;
bool visit[1005];
int v, m;
double xs, ys;
double xt, yt;
 
double distance(pair<double, double> a, pair<double, double> b) {
    double x = a.first - b.first;
    double y = a.second - b.second;
    return x*x + y*y;
}
 
int main() {
    scanf("%d %d", &v, &m);
    scanf("%lf %lf", &xs, &ys);
    scanf("%lf %lf", &xt, &yt);
 
    double ttx, tty;
    while (~scanf("%lf%lf", &ttx, &tty)) {
        b.push_back(mp(ttx, tty));
    }
    b.push_back(mp(xt, yt)); //도착점 삽입
 
    queue<pair<int, pair<double, double> > > q;
    q.push(mp(0, mp(xs, ys)));
    
    ll md = v * m * 60; // 이동할 수 있는 최대거리
    md *= md; // 최대거리의 제곱
 
    while (!q.empty()) {
        int cnt = -q.front().first;
        double x = q.front().second.first;
        double y = q.front().second.second;
        q.pop();
 
        if (x == xt && y == yt) {
            printf("Yes, visiting %d other holes.\n", cnt - 1);
            return 0;
        }
 
        for (int i = 0; i < b.size(); i++) {
            if (visit[i] || distance(mp(x, y), b[i]) > md) continue;
            visit[i] = 1;
            q.push(mp(-(cnt + 1), b[i]));
        }
    }
 
    puts("No.");
 
    return 0;
}