[백준 2307] 도로 검문 (C++)

문제 링크: www.acmicpc.net/problem/2307

2307번: 도로검문

1. 주의할 점

- 다익스트라 알고리즘에 대해 알고 있어야 한다

- 최단경로를 구했을 때, 경로를 구하는 방법을 알고 있어야 한다

 

2. 구현

- 종종 나오는 다익스트라의 심화문제라고 할 수 있다

- Dist[] 배열을 통해 1번 Node부터 각 Node까지의 최단거리를 저장한다

- Pre[A] 배열을 통해 Dist[A]의 값이 갱신되었다면(최단거리로) 어떤 Node에서 왔는지 저장한다

- V[] 벡터를 통해 모든 간선들에 대한 정보를 저장한다. 간선의 정보는 Info 구조체로, 도착점, 이동시간, 도로 사용가능 여부를 포함한다. 이때, 가장 처음에는 모든 간선들이 가능하므로 avail=true로 초기화한다.

- Dijkstra() 함수를 통해 1번 지점부터 이동할 수 있는 도로를 사용했을 때, 각 Node까지의 최단거리를 구한다

- 가장 처음에 Dijkstra() 함수를 통해 최단거리를 구하고 해당 값을 Shortest 변수에 저장한다

- getPath() 함수를 통해 최단거리에 사용된 도로를 1개씩 검문중으로 설정한다 -> make_reverse() 함수를 통해

- 검문 설정 이후, Dijkstra() 함수를 통해 검문중인 도로를 제외한 도로를 사용한 최단거리를 구하고 Delay에는 Dist[Node]의 최대값을 저장한다

- Dijkstra() 함수가 끝난 이후엔 검문중이던 도로를 해제하고 최단경로에 사용된 다른 도로를 검문한다

- 위의 과정을 최단경로에 사용된 모든 도로에 대해 수행한다

- Delay가 MAX라면 -1을 출력하고, MAX가 아니라면 Shortest와의 차이를 출력한다

#define MAX 987654321
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct info{
    int idx,val;
    bool avail=true;
};
struct cmp{
    bool operator()(info &a, info &b){
        return a.val > b.val;
    }
};
info tmp;
int dist[1001];
int pre[1001];      //현재 Node방문 전에 방문했던 Node
vector<info> v[1001];
int node,edge,from,to,val,shortest,delay=0;

void dijkstra(){
    priority_queue<info,vector<info>,cmp> pq;
    pq.push({1,0});
    for(int i=1;i<=node;i++)
        dist[i]=MAX;
    while(!pq.empty()){
        int cidx = pq.top().idx;
        int cv = pq.top().val;
        pq.pop();
        if(dist[cidx]<cv) continue;
        for(int i=0;i<v[cidx].size();i++){
            int next = v[cidx][i].idx;
            int nv = v[cidx][i].val;
            bool na = v[cidx][i].avail;
            if(!na) continue;       //검문중
            if(dist[next]>cv+nv){
                dist[next]=cv+nv;
                pre[next]=cidx;
                pq.push({next,cv+nv});
            }
        }
    }
}

void make_reverse(int a, int b, bool flag){
    for(int i=0;i<v[a].size();i++){
        int next = v[a][i].idx;
        if(next==b){
            v[a][i].avail=flag;
        }
    }
    
    for(int i=0;i<v[b].size();i++){
        int next = v[b][i].idx;
        if(next==a){
            v[b][i].avail=flag;
        }
    }
}

void getPath(){
    queue<int> q;
    q.push(node);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        if(now==1) break;
        int before = pre[now];
        q.push(before);
        make_reverse(now,before,false);
        dijkstra();
        delay = max(delay,dist[node]);
        make_reverse(now,before,true);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>node>>edge;
    for(int i=0;i<edge;i++){
        cin>>from>>to>>val;
        v[from].push_back({to,val});
        v[to].push_back({from,val});
    }
    dijkstra();
    shortest = dist[node];
    getPath();
    delay==MAX ? cout << -1 : cout << delay-shortest;
    return 0;
}