2307번: 도로검문

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


$O(m^2\lg m)$

각 간선을 제외시켜보며 얻은 최단 시간의 최댓값과 원래의 최단 시간 차를 구한다.

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int MXN = 1e4, MXM = 5e4;
int a[MXM], b[MXM], n, m, maxi;
vector<pair<int, int> > adj[MXN + 1];
int spath(int x, int y) {
    priority_queue<pair<int, int> > pq;
    int ck[MXN + 1] = {};
    pq.push({ 0,1 });
    while (!pq.empty()) {
        int h = pq.top().second, dis = -pq.top().first;
        pq.pop();
        if (h == n) return dis;
        if (ck[h]) continue;
        ck[h] = 1;
        for (auto it : adj[h]) if (x + y^h + it.first || x*y^h*it.first)
            pq.push({ -it.second - dis,it.first });
    }
    return 1e9;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, t; i < m; i++) {
        scanf("%d%d%d", a + i, b + i, &t);
        adj[a[i]].push_back({ b[i],t });
        adj[b[i]].push_back({ a[i],t });
    }
    for (int i = 0; i < m; i++) maxi = max(maxi, spath(a[i], b[i]));
    printf("%d", maxi < 1e9 ? maxi - spath(0, 0) : -1);
    return 0;
}

추가로 모든 간선을 제외하면서 최단 시간을 m번이나 구할 필요는 없다.
처음에 최단 시간을 만드는 경로를 구하자.
이 경로상의 간선을 제외하지 않는다면 그대로 최단 경로를 이용하면 되므로 지연시간은 0이 된다.
따라서 최단 경로 상의 최대 n개 간선 각각을 제외해보며 지연 시간을 따져주면 된다.
이 방법의 전체 시간복잡도는 $O(nm\lg n)$