[백준 2307] 도로검문

도둑이 최장시간으로 도시를 빠져나가게 경찰이 도로 하나를 막아야하는 시나리오이다.

 

우선 도둑이 최단시간으로 빠져나갈 수 있는 경로를 찾아야한다.

따라서 다익스트라를 돌리되, 각 노드들에 대해 최단시간이 갱신됨에 따라 그 노드 직전 노드를 기록함으로써

다익스트라가 끝났을때 최단경로를 구성하는 노드들을 찾을 수 있어야한다.

 

이때 최단경로를 기록해야하는 이유는 경찰이 막을 도로에 대한 후보군을 최단경로를 구성하는 노드들로 좁혀줘야하기 때문이다.

왜냐하면 최단경로를 구성하지 않는 노드일 경우 막아봤자 의미가 없기 때문이다.

 

따라서 다익스트라에서 최단경로를 구성하는 노드들을 찾고

해당 경로들을 한개씩 빼본 상황을 돌려가면서 답을 찾아야한다.

 

이때 중요한게 최단경로를 구성하는 노드를

vector<int> parents[SIZE];

 

여기에 저장해주는데 그냥 int parent[SIZE]; 이런 배열에 저장하면 안되는 이유가

그냥 일차원 배열로 할 경우 만약 최단경로가 여러개라면

그 중 하나만 기록가능하기 때문이다.

 

따라서 각 노드의 parent 노드를 저장할때 vector로 저장해서

여러 경로가 존재할때 해당 부모 노드들을 다 저장할 수 있게 해야한다.

 

예를 들어 1 > 2 > 4 > 5 와 1 > 3 >4 > 5 가 가능한 경우라면

4의 직전 노드 즉, parent[4] 에 대한 값으로 2와 3을 모두 가지고 있어야

도둑이 최단경로로 갈 수 있는 모든 경로를 기록할 수 있기 때문이다.

 

만약 배열로 한다면 4의 직전 노드로 2 또는 3 둘 중 하나만 기록되기 때문에,

둘 중 다익스트라를 돌때 더 늦게 갱신되는 노드로 기록되기 때문에,

모든 최단경로를 구성하는 노드를 기록하지 못하고

따라서 경로를 하나씩 뺄때 고려해야하는 노드지만, 고려를 안하는 경우가 생기기 때문이다.

 

---

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <tuple>

#define SIZE 1001
#define INF int(1e9)

using namespace std;

int N, M;

vector<vector<pair<int, int>>> graph(SIZE);
vector<int> parents[SIZE];
int blocked[SIZE][SIZE] = {
    0,
};
int dist[SIZE] = {
    0,
};
int ans1 = INF;
int ans2 = 0;

/**
최단경로가 여러개일때에 대한 예시
6 7
1 2 1
1 4 2
3 6 1
4 5 1
2 3 2
3 4 1
5 6 2
**/

// 아무 도로 안막았을때
void solve1()
{
    for (int i = 1; i <= N; i++)
    {
        dist[i] = INF;
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, 1));
    dist[1] = 0;

    while (!pq.empty())
    {
        int total = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        // 조사할 필요가 없으면
        if (dist[cur] < total)
        {
            continue;
        }

        for (int i = 0; i < graph[cur].size(); i++)
        {
            int next = graph[cur][i].first;
            int cost = graph[cur][i].second;

            // 조사할 필요가 있다면
            if (total + cost < dist[next])
            {
                dist[next] = total + cost;
                // 부모노드 초기화하고
                parents[next].clear();
                // 추가해주기
                parents[next].push_back(cur);
                pq.push(make_pair(total + cost, next));
                continue;
            }

            // 기존 값과 동일한 값이면
            if (dist[next] == total + cost)
            {
                // 부모노드 하나 더 있다고 추가만 하기
                parents[next].push_back(cur);
            }
        }
    }
}

void solve2()
{
    for (int i = 1; i <= N; i++)
    {
        dist[i] = INF;
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, 1));
    dist[1] = 0;

    while (!pq.empty())
    {
        int total = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        // 조사할 필요가 없으면
        if (dist[cur] < total)
        {
            continue;
        }

        for (int i = 0; i < graph[cur].size(); i++)
        {
            int next = graph[cur][i].first;
            int cost = graph[cur][i].second;

            // 검문중인 도로면
            if (blocked[cur][next] == 1)
            {
                continue;
            }

            // 조사할 필요가 있다면
            if (total + cost < dist[next])
            {
                dist[next] = total + cost;
                pq.push(make_pair(total + cost, next));
            }
        }
    }

    // 검문중인 도로 하나 막았는데 도착할 수 없다면
    if (dist[N] == INF)
    {
        ans2 = INF;
    }
    // 검문중인 도로 하나 막았는데 도착가능하다면
    // 기존꺼랑 비교해서 더 최단시간으로 갈 수 있다면 최신화
    else if (dist[N] > ans2)
    {
        ans2 = dist[N];
    }
}

vector<pair<int, int>> routes;

void getRoutes()
{
    int check[SIZE] = {
        0,
    };

    queue<int> q;
    q.push(N);
    check[N] = 1;

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        for (int i = 0; i < parents[cur].size(); i++)
        {
            int parent = parents[cur][i];

            // 아직 방문 안했으면
            if (!check[parent])
            {
                // parent -> cur로 가는 경로 추가
                routes.push_back(make_pair(parent, cur));
                check[parent] = 1;
                q.push(parent);
            }
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    int start, end, cost;
    for (int i = 0; i < M; i++)
    {
        cin >> start >> end >> cost;
        graph[start].push_back(make_pair(end, cost));
        graph[end].push_back(make_pair(start, cost));
    }

    solve1();

    ans1 = dist[N];

    getRoutes();

    for (int i = 0; i < routes.size(); i++)
    {
        start = routes[i].first;
        end = routes[i].second;

        blocked[start][end] = 1;
        blocked[end][start] = 1;
        solve2();
        blocked[start][end] = 0;
        blocked[end][start] = 0;

        // 특정 도로를 검문했을때 도둑이 도착못하면 최상의 결과
        if (ans2 == INF)
        {
            break;
        }
    }

    if (ans2 == INF)
    {
        cout << "-1";
    }
    else
    {
        cout << ans2 - ans1;
    }

    return 0;
}