[백준 5719번] 거의 최단 경로

문제 링크: https://www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

<문제 풀이> 다익스트라 알고리즘

 

다익스트라로 최단 거리를 갱신하고, 가능한 모든 최단 경로 삭제 후 다시 다익스트라로 최단거리를 갱신하면 됩니다.

 

최단 경로를 삭제하기 위해 각 정점에 도달하기 전의 정점을 기록할 수 있는 자료구조가 필요합니다. 이때 가능한 최단거리가 여러 개 있을 수 있으므로 vector<int> 타입의 배열을 사용하여 이전 정점들을 저장해야 합니다.

 

제거할 때는 최단 경로 배열을 가지고 도착점에서 출발점까지 BFS를 호출하면서 간선을 제거해 줍니다.

간선 제거는 2차원 배열로 표현할 수 있습니다.

removed[i][j] = true; // i -> j 간선 제거

 

 

<C++소스코드>

 

#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;

vector<pair<int, int> >adj[500];
vector<int> pre[500];
bool removed[500][500];

const int INF = 0x3f3f3f3f;

int d[500];

void init() {
    for (int i = 0; i < 500; i++) {
        adj[i] = {};
        for (int j = 0; j < 500; j++) {
            removed[i][j] = false;
        }
    }
}

void EraseEdge(int start, int end) {
    int cur = end;
    queue<int> Q;
    Q.push(cur);
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (auto u : pre[cur]) {
            if (removed[u][cur]) continue;
            removed[u][cur] = true;
            Q.push(u);
        }
    }
}

int dijkstra(int start, int end) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    for (int i = 0; i < 500; i++) {
        pre[i] = {};
    }
    memset(d, 0x3f, sizeof(d));

    d[start] = 0;
    pq.push({ d[start], start });

    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        int dist = cur.first;
        int curIdx = cur.second;
        if (d[curIdx] != dist) continue;
        for (auto& nxt : adj[curIdx]) {
            int cost = nxt.first;
            int nIdx = nxt.second;
            
            if (removed[curIdx][nIdx]) continue;

            if (d[curIdx] + cost == d[nIdx]) {
                pre[nIdx].push_back(curIdx);
            }
            if (d[curIdx] + cost < d[nIdx]) {
                d[nIdx] = d[curIdx] + cost;
                pre[nIdx].clear();
                pre[nIdx].push_back(curIdx);
                pq.push({ d[nIdx], nIdx });
            }
        }
    }
    if (d[end] >= INF) return -1;
    return d[end];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    while (true) {
        init();
        vector<int> ans;
        int N, M; cin >> N >> M;
        if (N == 0 && M == 0) break;

        int S, D; cin >> S >> D;
        for (int i = 0; i < M; i++) {
            int u, v, w; cin >> u >> v >> w;
            adj[u].push_back({ w, v });
        }
        dijkstra(S, D);
        EraseEdge(S, D);
        cout<<dijkstra(S, D)<<'\n';
   
    }
    
    return 0;
}