[백준] 2325 - 개코전쟁

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

2325번: 개코전쟁

 

이전에 비슷한 문제를 풀어봐서 쉽게 풀 수 있었던 문제이다.

간선의 개수가 최대 약 50만 개가 주어지므로, 모든 간선을 없애면서 다익스트라를 수행하는 것은 불가능하다.

하지만 모든 간선을 다 체크해 볼 필요가 있을까?

 

예제 1번에서 최단 거리는 1 -> 2 -> 4 -> 5이다.

여기서 1-3 또는 2-3 또는 2-5 간선을 없앴다고 해서 최단 거리가 변경이 될까? 그렇지 않을 것이다.

따라서 핵심은 최단 거리에 포함되는 간선을 제거해 보는 것이다.

 

이를 위해서 pre[i] = 최단 경로로 탐색 시, i번 정점 이전에 방문한 정점으로 정의한 배열을 준비하자.

처음 다익스트라로 pre 배열을 채울 수 있을 것이고, 이후 i = n부터 i = 1이 될 때까지 각각 i-pre[i] 간선을 사용하지 않으며 다익스트라를 돌리면 최단거리의 최댓값을 구할 수 있다.

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<vector<pair<int, int>>> v(1001);
int n, m, pre[1001];

vector<int> dijk(int k) {
    vector<int> dis(n + 1, 987654321);
    priority_queue<pair<int, int>> q;
    dis[1] = 0;
    q.push({0, 1});

    while (!q.empty()) {
        int cost = -q.top().first;
        int node = q.top().second;
        q.pop();
        
        if (cost > dis[node]) {
            continue;
        }

        for (auto &i : v[node]) {
            int nxNode = i.first;
            int nxCost = cost + i.second;
            
            if ((node == k && pre[node] == nxNode) || (nxNode == k && pre[nxNode] == node)) {
                continue;
            }
            if (nxCost < dis[nxNode]) {
                if (k == 0) {
                    pre[nxNode] = node;
                }
                dis[nxNode] = nxCost;
                q.push({-nxCost, nxNode});
            }
        }
    }
    return dis;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    dijk(0);
    int ans = 0;
    for (int i = n; i > 1;) {
        vector<int> dis = dijk(i);
        i = pre[i];
        ans = max(ans, dis[n]);
    }
    cout << ans;
}