거의 최단 경로

백준 5719번: 거의 최단 경로

아이디어

최단 경로에 포함되는 모든 간선을 지나면 안된다. 최단 경로가 여러개인 경우 전부 지나면 안된다. 따라서 최단경로의 길이를 구하고, 다음 최단 경로의 길이가 바뀔 때까지 경로를 지우는 방법을 사용하려고 했으나 실패했다.

0->2->3 을 최단경로로 찾고 해당하는 간선을 지운다. 지운 후에 다시 최단 경로를 찾으면 0->1->3이 최단 경로이다. 하지만 맨 처음에 0->1->2->3도 최단 경로에 포함되기 때문에 0->1 간선을 사용할 수 없다.

어떻게 하면 모든 최단 경로를 다 지울 수 있을까?

다익스트라를 한 번 돌린다. 목적지부터 시작해서 나(n)한테 오는 간선이 존재하는지 확인(x->n)하고, 존재한다면 시작점부터 x까지의 최단 거리 + x->n 거리와 시작점부터 n까지의 최단 거리를 비교한다. 같다면 x->n 간선은 최단 경로에 포함되는 것이다. 이를 모두 찾아서 지우고, 다시 다익스트라를 한 번 돌려주면 거의 최단 경로를 찾을 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 500, INF = 2e9;
int graph[MAX][MAX], dist[MAX];
bool visited[MAX];

void dijkstra(int n, int s) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    fill(dist, dist+MAX, INF);
    memset(visited, 0, sizeof(visited));
    dist[s] = 0;
    while (!pq.empty()) {
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if (visited[cur]) continue;
        visited[cur] = true;
        for (int i = 0; i < n; i++) {
            if (!graph[cur][i] || visited[i]) continue;
            if (dist[i] > cost+graph[cur][i]) {
                dist[i] = cost+graph[cur][i];
                pq.push({cost+graph[cur][i], i});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    while (1) {
        int n, m;
        cin >> n >> m;
        if (!n && !m) break;
        int s, d;
        cin >> s >> d;
        memset(graph, 0, sizeof(graph));
        for (int i = 0; i < m; i++) {
            int u, v, p;
            cin >> u >> v >> p;
            graph[u][v] = p;
        }

        dijkstra(n, s);
        if (dist[d] == INF) {
            cout << -1 << '\n';
            continue;
        }
        queue<int> q;
        vector<pair<int, int>> v;
        q.push(d);
        memset(visited, 0, sizeof(visited));
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            if (visited[cur]) continue;
            visited[cur] = true;
            for (int i = 0; i < n; i++) {
                if (!graph[i][cur]) continue;
                if (dist[cur] == dist[i]+graph[i][cur]) {
                    v.push_back({i, cur});
                    q.push(i);
                }
            }
        }
        for (auto p : v) {
            graph[p.first][p.second] = 0;
        }

        dijkstra(n, s);
        if (dist[d] == INF) cout << -1 << '\n';
        else cout << dist[d] << '\n';
    }
    return 0;
}

여담

bfs처럼 큐에 넣고 최단 경로에 포함되는 간선을 찾는다. 엄청 어려웠다..