백준 16318번 Delivery Delays

문제 요약

정점 $n$개, 간선 $m$개의 무방향 그래프가 주어진다. 해당 그래프의 1번 노드에 피자집이 있다. $k$개의 피자 주문이 들어오는데 각 주문은 $s_i, u_i, t_i$로 들어오는데 각각 주문이 들어온 시각, 주문이 들어온 노드의 번호, 해당 주문의 피자가 완성되는 시간이다.

이 피자들을 주문이 들어온 순서대로 배달하려고 한다. 시각 0에 1번 정점에 위치하며, 들고다닐 수 있는 피자의 수에 제한은 없다. 이 때, 각 주문의 대기시간의 최댓값을 최소화 하여라.

$ n \le 1000$, $ m \le 5000$, $ k \le 1000$, $ 0 \le s_i \le t_i \le 10^8 $

풀이

들고다닐 수 있는 피자의 수에 제한이 없으므로 피자집에서 다른 피자가 준비 완료될 때까지 기다렸다가 그것까지 같이 들고나가서 배달을 하는 것이 가능하다. 이 때 어떻게 배달경로를 잡아야 할 지 생각해보자.

간단하게 생각하기 위해서 1번 주문의 피자부터 $i$번 주문의 피자까지를 들고 피자집에서 출발했다고 하자.

그러면 이 피자들을 최대한 빨리 순서대로 배달하기 위해서는 각 주문과 주문 사이를 최단경로로 움직여야 함은 명확하다.

이를 통해서 알 수 있는 것은 $i$번 주문부터 $j$번 주문까지의 피자를 들고 1번정점에서 나왔다면 1번 정점에서 $i$번 정점까지 최단 거리로, $i$번 정점에서 $i+1$정점까지 최단거리로, ... , $j-1$번 정점에서 $j$번 정점까지 최단거리로 움직여야 제일 빠르게 배달한다는 것이다.

즉, 지금 내가 처리할 주문의 범위를 정하면 경로는 고정된다는 것이다.

배달을 순서대로 진행했을 때 모든 주문의 대기시간이 $T$보다 작거나 같은가에 대한 결정문제를 위 사실을 이용하면 풀 수 있다.

아래와 같은 dp식을 생각해보자
$$
\begin{gather}
dp(i) = \text{조건을 만족하며 i번 주문까지 처리하고 1번으로 돌아왔을 때의 최소 시각} \\
dp(i) = \underset{j \le i}{min}{(dp(j-1)+D(j, i))}
\end{gather}
$$
여기서 $D(j,i)$는 $j$번 주문부터 $i$번 주문까지를 처리하고 1번 정점으로 돌아오는 시간이다. 이 값은 $O(N^3)$혹은 $O(NMlogM)$에 전처리가 가능하다.

이 값을 이용하면 $j$번 주문부터 $i$번 주문까지를 처리할 때 조건을 만족하는지 알 수 있다.

1번 정점에서 출발하는 시각은 $b_{j,i}=max(dp(j-1), t_i)$가 될 것이고, 주문들을 처리하며 $i$번 정점에 도달하는 시각 $a_{j,i}=b_{j.i}+D(j,i)-dist_i$가 될 것이다. 여기서 $dist_i$는 1번 정점부터 $i$번 정점까지의 거리다.

이 때, 각 주문 $order_k$의 대기시간은 $a_{j,i} - D(k, i) + dist_k + dist_i - s_k$가 될 것이다.

이를 나이브하게 구하면 $O(N^3)$이 걸리지만 $i$를 고정했을 때, $a_{j,i}, b_{j,i}$는 $j$가 바뀌면서 변화하지만 빼주는 값들은 변하지 않는 것을 알 수 있다. 따라서, 이 값들의 최솟값만 유지하면서 갱신해나가면 결정문제를 $O(N^2)$에 해결할 수 있다.

이제 결정문제가 빠른 시간에 해결되니 답을 이분탐색하면 된다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int N, M, K;
vector<vector<pair<int, ll>>> G(1005);
vector<vector<ll>> dist(1005, vector<ll>(1005, INF));
ll s[1005], u[1005], t[1005];
ll dp[1005];    // minimum time to deliver 1...i and back to 1
ll psum[1005];

void dijkstra(vector<ll> &dist, int src) {
    priority_queue<pair<ll,int>, vector<pair<ll, int>>, greater<>> pq;
    dist[src] = 0;
    pq.emplace(dist[src], src);
    while(!pq.empty()) {
        int cur = pq.top().second;
        ll d = pq.top().first;
        pq.pop();
        if(dist[cur] < d) continue;
        for(pair<ll,int> p : G[cur]) {
            int v = p.first;
            ll w = p.second;
            if(dist[v] > d + w) {
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
        }
    }
}

bool check(ll waiting_time) {
    for(int i=0;i<=K;++i) dp[i] = INF;
    dp[0] = 0;
    for(int i=1;i<=K;++i) {
        bool flag = false;
        ll mi = INF;
        for(int j=i;j>0;--j) {   // [j, i]
            ll start_time = max(dp[j-1], t[i]);
            ll arrival_time = start_time + psum[i] - psum[j] + dist[1][u[j]];
            mi = min(mi, s[j] + psum[i] - psum[j]);
            if(arrival_time - mi <= waiting_time) {
                dp[i] = min(dp[i], arrival_time + dist[1][u[i]]);
                flag = true;
            }
        }
        if(!flag) return false;
    }
    return true;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M;
    for(int i=0;i<M;++i) {
        int u, v, w; cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    for(int i=1;i<=N;++i) dijkstra(dist[i], i);
    cin >> K;
    for(int i=1;i<=K;++i) cin >> s[i] >> u[i] >> t[i];
    u[0] = 1;
    for(int i=1;i<=K;++i) psum[i] = psum[i-1] + dist[u[i-1]][u[i]];
    ll lo = 0, hi = INF;
    while(lo < hi) {
        ll mid = lo + hi >> 1;
        if(check(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << hi << '\n';
    return 0;
}