9988번: Roadblock

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


$O(n^3)$

먼저, 최단 경로를 구해 놓는다.
이 경로를 제외한 나머지 간선을 지연시키면 전체 그래프에서 최단 경로는 바뀌지 않는다.
따라서 최단 경로에 존재하는 각각의 간선을 지연시켜보며 최대 n번만 최단 경로를 구하면 된다.

#include<cstdio>
const int MXN = 250;
int n, m, adj[MXN + 1][MXN + 1], path[MXN + 1], tpath[MXN + 1];
int spath() {
    int dis[MXN + 1], ck[MXN + 1] = {};
    dis[1] = 0;
    for (int i = 2; i <= n; i++) dis[i] = 1e9;
    for (int j = 1; j < n; j++) {
        int pos, maxi = 1e9;
        for (int i = 1; i <= n; i++) if (!ck[i] && dis[i] < maxi) {
            maxi = dis[i];
            pos = i;
        }
        ck[pos] = 1;
        for (int i = 1; i <= n; i++) if (maxi + adj[pos][i] < dis[i]) {
            dis[i] = maxi + adj[pos][i];
            path[i] = pos;
        }
    }
    return dis[n];
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) adj[i][j] = 1e9;
    for (int i = 0, a, b, l; i < m; i++) {
        scanf("%d%d%d", &a, &b, &l);
        adj[a][b] = adj[b][a] = l;
    }
    int opt = spath(), maxi = 0;
    for (int i = 1; i <= n; i++) tpath[i] = path[i];
    for (int i = n; i ^ 1; i = tpath[i]) {
        adj[i][tpath[i]] *= 2; adj[tpath[i]][i] *= 2;
        int t = spath();
        if (t > maxi) maxi = t;
        adj[i][tpath[i]] /= 2; adj[tpath[i]][i] /= 2;
    }
    printf("%d", maxi - opt);
    return 0;
}