1909 냄새 싫어

n명의 냄새나는 사람이 주어질 때 sx,sy에서 tx,ty로 가는 경로중에

경로중의 임의의 점에서 냄새나는 사람들과의 직선거리 중 최소값이 가장 큰 경로를 구하는 문제다.

이렇게쓰면 이해가 어려울 수 있는데 돌려말하자면 경로중에 최악의 경우에 냄새나는 사람과의 거리가 가장 먼 경로를 구하면 된다.

임의의 경로 t1에서 경로를 이동중에 냄새나는 사람과의 직선거리를 배열로 만들었을 때 [ 3, 7, 1, 16, 4, 7 ] 이라고 하고

또다른 경로 t2에서도 마찬가지 배열을 만들었을 때 [ 2, 4, 3, 5, 4, 2 ] 이라고 한다면

우리는 t2를 골라야 한다. t1에서 직선거리중 가장 짧은게 1이었고 t2에서는 2기 때문이다.

해결법

1. n개의 점을 입력받으면서 큐에 넣는다.

2. 큐를 가지고 점 i,j에서 가장 가까운 냄새나는 사람까지의 거리를 계산해놓는다.

3. sx,sy에서 tx,ty까지 다익스트라를 돌린다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;
 
typedef pair<int, int> pii;
 
int h, w, sx, sy, tx, ty;
int n, dx[] = { 0,0,1,-1,-1,-1,1,1 }, dy[] = { 1,-1,0,0,-1,1,-1,1 };
int a[1000011], b[1000011];
int d[1001][1001], d2[1001][1001];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    memset(d, 0x3f, sizeof(d));
    cin >> w >> h;
    // h : x, w : y
    cin >> sy >> sx >> ty >> tx >> n;
    queue<pair<pii, int>> q;
    int minv = 1e9, mx = 0, my = 0, mi = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        q.push({ { b[i],a[i] },i });
        d[b[i]][a[i]] = 0;
    }
    while (q.size()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int st = q.front().second;
        q.pop();
        for (int i = 0; i < 8; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nc = ((b[st] - nx)*(b[st] - nx) + (a[st] - ny)*(a[st] - ny));
            if (nx < 1 || ny < 1 || nx > h || ny > w || d[nx][ny] <= nc) continue;
            q.push({ { nx,ny },st });
            d[nx][ny] = nc;
        }
    }
    memset(d2, -1, sizeof(d2));
    priority_queue<pair<int, pii>> q2;
    q2.push({ d[sx][sy],{ sx,sy } });
    while (q2.size()) {
        int c = q2.top().first;
        int x = q2.top().second.first;
        int y = q2.top().second.second;
        q2.pop();
        if (d2[x][y] != -1) continue;
        d2[x][y] = c;
        if (x == tx && y == ty) break;
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 1 || ny < 1 || nx > h || ny > w || d2[nx][ny] != -1) continue;
            q2.push({ min(c,d[nx][ny]),{ nx,ny } });
        }
    }
    cout << d2[tx][ty];
    return 0;
}