백준 2307번 도로검문 - C++ 풀이

---

 

1. 다익스트라 알고리즘을 사용해서 최단 시간과 최단 경로를 구한다.
2. 최단 경로에 속한 간선들만 하나씩 지워보면서 최대 지연 시간을 찾는다.

 

1. 다익스트라 알고리즘을 사용해서 최단 시간과 최단 경로를 구한다.

 먼저 검문을 하지 않았을 때 최단 시간을 알아야 지연 시간을 계산할 수 있다. 다익스트라 알고리즘을 사용해서 최단 시간을 구한다.

 이때 최단 경로도 함께 구해둔다. 최단 경로에 포함되지 않은 도로를 검문해봤자 용의자가 최단 경로로 이동하면 지연시간이 0이기 때문에, 지연 시간을 최대로 하기 위해서는 최단 경로에 포함된 도로에서 검문을 해야 하기 때문이다.

 

2. 최단 경로에 속한 간선들만 하나씩 지워보면서 최대 지연 시간을 찾는다.

 간선을 하나 지웠을 때 용의자의 최단 이동 시간도 다익스트라를 통해 구할 수 있다. 위에서 설명한 바와 같이 최단 경로에 속하는 간선들에 대해서만 이 작업을 해주면 된다.

 

반응형

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii;
const int INF = 987654321;

int N, M;
vector<pii> adjs[1001];
int before[1001];

bool isSameEdge(pii lhs, pii rhs) {
    if (lhs.first == rhs.first && lhs.second == rhs.second) return true;
    if (lhs.first == rhs.second && lhs.second == rhs.first) return true;
    return false;
}

int dijkstra(int from, int to, pii exceptedEdge) {
    vector<int> dist(N+1, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    
    dist[from] = 0;
    pq.push({0, from});
    
    while (!pq.empty()) {
        int d = pq.top().first;
        int curr = pq.top().second;
        pq.pop();
        
        if (d > dist[curr]) continue;
        
        for (auto adj: adjs[curr]) {
            int w = adj.first;
            int next = adj.second;
            
            if (isSameEdge({curr, next}, exceptedEdge)) continue;
            
            if (d + w < dist[next]) {
                dist[next] = d + w;
                pq.push({dist[next], next});
                if (exceptedEdge == make_pair(-1, -1)) before[next] = curr;
            }
        }
    }
    
    return dist[to];
}

int solution() {
    int minDist = dijkstra(1, N, {-1, -1});
    int maxDist = 0;
    
    // 최단경로에 포함된 간선 하나씩 지워보기
    for (int curr = N; curr != 0; curr = before[curr]) {
        maxDist = max(maxDist, dijkstra(1, N, {curr, before[curr]}));
    }
    
    if (maxDist == INF) return -1;
    else return maxDist - minDist;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    
    for (int i=0; i<M; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        adjs[a].push_back({t, b});
        adjs[b].push_back({t, a});
    }
    
    cout << solution();

    return 0;
}