백준 26966, Breakdown

 

 

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

 

26966번: Breakdown

 

 

요약

 

 

가중치가 있는 방향그래프가 주어진다. 정점의 개수 N과 K가 주어질 때, 간선을 순서대로 삭제하여 정확히 K번 간선을 사용하여 1번 정점에서 N번 정점으로 가는 최단거리를 매번 구해보자.

---

1. 초기 그래프는 $ N\leq  300$이고, 모든 정점쌍 (i, j) 간에 간선이 $N^2$개 존재하는 그래프이다. 간선이 삭제될 때마다 다익스트라를 돌리는 방식은 제한 내에 수행될 수 없다.

 

2. 그래프에서 간선 삭제는 처리하기 까다로우므로, 모든 과정을 뒤집어서 생각하자. 처음에 간선이 존재하지 않는 그래프에서 역으로 간선을 추가할 것이다. 

 

3. $ K\leq  8$ 이라는 사실에 주목하자. 모든 쿼리는 1번 정점에서 N번 정점으로 향하는 경로를 물어보므로, 매 쿼리마다 $ 1\to i$, $i\to N$의 두 가지 경로로 쿼리를 나누어 생각할 수 있다. 그렇다면 $K \leq 4$ 의 제한으로 문제를 바꿀 수 있다.

 

4. 다음과 같이 세 개의 dp 상태를 정의하여 보자.

$dp1[i][k]$: 1번 정점에서 i번 정점까지 k개의 간선을 사용하였을 때의 최단거리, $k \leq 4$

$dp2[i][k]$: i번 정점에서 N번 정점까지 k개의 간선을 사용하였을 때의 최단거리, $k \leq 4$

$dp3[i][j][k]$: i번 정점에서 j번 정점까지 k개의 간선을 사용하였을 때의 최단거리, $k \leq 2$

 

5. $ a \to b$ 간선이 추가될 때 마다 케이스별로 나누어 dp table을 갱신해 주도록 하자.

$dp3[a][b][1] = min(dp3[a][b][1], W[a][b]) $

$dp3[a][i][2] = min(dp3[a][i][2], W[a][b] + dp3[b][i][1]) $, $dp3[i][b][2] = min(dp3[i][b][2], W[a][b] + dp3[i][a][1]) $

 

$ k = 1$ 과 $k = 2$인 경우는 $dp3$을 활용하여 최솟값을 채워준다.

$ k = 3$ 인 경우, $ a \to b$ 간선이 경로의 첫 번째, 두 번째, 세 번째 간선으로 사용됐을 때로 나누어 채워준다.

마찬가지로, $ k = 4$ 인 경우 $ a \to b$ 간선이 경로의 첫 번째, 두 번째, 세 번째, 네 번째 간선으로 사용됐을 때로 나누어 채워준다.

 

5. 전체 시간 복잡도는 $O(N^3)$을 넘지 않는다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;

int N, K;
ll W[305][305];
vector<pii> edge;
ll ans[305 * 305];
ll dp1[305][5], dp2[305][5], dp3[305][305][3];

void add_edge(int a, int b) {
    ll w = W[a][b];

    dp3[a][b][1] = min(dp3[a][b][1], w);

    for (int i = 1; i <= N; i++) dp3[a][i][2] = min(dp3[a][i][2], w + dp3[b][i][1]);
    for (int i = 1; i <= N; i++) dp3[i][b][2] = min(dp3[i][b][2], dp3[i][a][1] + w);

    for (int i = 1; i <= N; i++) {
        dp1[i][1] = min(dp1[i][1], dp3[1][i][1]);
        dp2[i][1] = min(dp2[i][1], dp3[i][N][1]);
    }

    for (int i = 1; i <= N; i++) {
        dp1[i][2] = min(dp1[i][2], dp3[1][i][2]);
        dp2[i][2] = min(dp2[i][2], dp3[i][N][2]);
    }

    for (int i = 1; i <= N; i++) {
        dp1[i][3] = min(dp1[i][3], dp3[1][a][1] + w + dp3[b][i][1]);
        dp2[i][3] = min(dp2[i][3], dp3[i][a][1] + w + dp3[b][N][1]);

        if (a == 1) dp1[i][3] = min(dp1[i][3], w + dp3[b][i][2]);
        if (a == i) dp2[i][3] = min(dp2[i][3], w + dp3[b][N][2]);

        if (b == i) dp1[i][3] = min(dp1[i][3], dp3[1][a][2] + w);
        if (b == N) dp2[i][3] = min(dp2[i][3], dp3[i][a][2] + w);
    }

    for (int i = 1; i <= N; i++) {
        dp1[i][4] = min(dp1[i][4], dp3[1][a][1] + w + dp3[b][i][2]);
        dp2[i][4] = min(dp2[i][4], dp3[i][a][1] + w + dp3[b][N][2]);

        dp1[i][4] = min(dp1[i][4], dp3[1][a][2] + w + dp3[b][i][1]);
        dp2[i][4] = min(dp2[i][4], dp3[i][a][2] + w + dp3[b][N][1]);

        if (a == 1) for (int j = 1; j <= N; j++) dp1[i][4] = min(dp1[i][4], w + dp3[b][j][1] + dp3[j][i][2]);
        if (a == i) dp2[i][4] = min(dp2[i][4], w + dp2[b][3]);

        if (b == i) dp1[i][4] = min(dp1[i][4], dp1[a][3] + w);
        if (b == N) for (int j = 1; j <= N; j++) dp2[i][4] = min(dp2[i][4], dp3[i][j][2] + dp3[j][a][1] + W[a][b]);
    }

    return;
}

void solve() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) cin >> W[i][j];
    }

    for (int i = 0; i < N * N; i++) {
        int a, b;
        cin >> a >> b;
        edge.emplace_back(a, b);
    }

    reverse(edge.begin(), edge.end());

    memset(dp1, INF, sizeof(dp1));
    memset(dp2, INF, sizeof(dp2));
    memset(dp3, INF, sizeof(dp3));

    for (int i = 0; i < edge.size(); i++) {
        ll now = INF;
        for (int j = 1; j <= N; j++) {
            int half = K / 2;
            now = min(now, dp1[j][half] + dp2[j][K - half]);
        }

        if (now == INF) ans[i] = -1;
        else ans[i] = now;

        int a = edge[i].first, b = edge[i].second;
        add_edge(a, b);
    }

    for (int i = N * N - 1; i >= 0; i--) cout << ans[i] << '\n';

    return;
}

int main(void) {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) solve();
    return 0;
}