[BAE/<JOON> 문제풀이] 11952. 좀비

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

11952번: 좀비

 

서론

그래프 문제여도 최적화에 대한 아이디어가 들어가 있어서 풀이를 작성했다.

---

풀이

핵심은 해처리로부터의 거리가 s 이상인 정점들을 효율적으로 구분하는 것이다.

당연히 정점을 방문할 때마다 거리가 s이하인 점들을 순회하면 TLE 가 난다.

토마토 문제를 풀 때 처럼 모든 해처리 위치를 큐에 집어넣고 각 해처리마다 거리가 s 인 점들을 모두 위험하다고 표시하면 된다. 그런데, 이렇게 해도 출발 도착점을 제외한 모든 정점이 해처리이고 허용 거리가 크다면 최대 방문 횟수는 100000 ^ 3 이므로 TLE를 피할 수 없다. ( 실제로 그런 입력은 주어지지 않지만 해처리가 많은 입력을 대략적으로 표현했다.)

이를 피하는 방법은 해처리가 아닌 노드를 위험으로 표시할 때 가장 가까운 해처리까지의 거리를 갱신하면 된다.

이후에 멀리서 온 다른 해처리 탐색이 그 정점을 방문했을 때는 굳이 탐색을 지속할 필요가 없다.

어차피 가장 가까운 해처리에서 온 탐색이 멀리서 온 탐색이 탐색할 정점을 모두 탐색해 위험 상태로 바꿔 줄 것이기 때문이다. 이런 방식으로 정점 당 최대 1번까지만 탐색을 하도록 최적화를 할 수 있다. 

이 후 최단거리 탐색은 Dijkstra 니까 굳이 설명하지 않겠다.

---

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long; 
const ll ulm = 9223372036854775807;
struct line {
    ll s, e, cnt;
};
bool cmp(line a, line b) {
    return a.s < b.s;
}
struct cmpc {
    bool operator()(line a, line b) {
        return a.cnt > b.cnt;
    }
};
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    ll n, m, k, s; cin >> n >> m >> k >> s; vector<vector<ll>> arr(n + 1); vector<line> fee(n + 1); vector<ll> ch(n + 1, ulm);
    ll safe, dang; cin >> safe >> dang;
    for (ll i = 1; i <= n; i++) {
        fee[i].s = safe; fee[i].e = dang;
    }
    queue<line> q;
    vector<ll> sch(n + 1);
    for (ll i = 1; i <= k; i++) {
        ll d; cin >> d;
        q.push({ d, d, s + 1 });
        sch[d] = ulm;
    }
    for (ll i = 1; i <= m; i++) {
        ll s, e; cin >> s >> e;
        arr[s].push_back(e);
        arr[e].push_back(s);
    }
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        for (auto nx : arr[cur.e]) {
            if (sch[nx] >= cur.cnt - 1) continue;
            sch[nx] = cur.cnt - 1;
            fee[nx].s = fee[nx].e;
            q.push({ nx, nx, cur.cnt - 1 });
        }
    }
    priority_queue<line, vector<line>, cmpc> pq;
    pq.push({ 1, 1, 0 });
    ch[1] = 0;
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        if (cur.e == n) {
            cout << cur.cnt - fee[n].s;
            return 0;
        }
        for (auto nx : arr[cur.e]) {
            if (sch[nx] == ulm) continue;
            if (ch[nx] <= cur.cnt + fee[nx].s) continue;
            ch[nx] = cur.cnt + fee[nx].s;
            pq.push({ nx, nx, cur.cnt + fee[nx].s });
        }
    }
    return 0;
}