백준[5719] 거의 최단 경로

거의 최단 경로

문제 링크

http://icpc.me/5719

5719번: 거의 최단 경로

풀이

다익스트라를 두 번 돌려서 풀 수 있다.

최단 경로로 오기 위한 모든 경로를 처음 다익스트라를 돌릴 때 prv 벡터에 어디서 온 건지 저장해놓는다.

이때 dist 값이 변경될 때 이차원 벡터를 초기화하고 그 벡터에 넣는 방식으로 구현했다.

그런 후 dfs를 통해 최단 경로들을 모두 없앤다. 이때 중복되는 dfs를 제거하지 않으면 최대 재귀 호출을 10^4만큼 시간 초과가 발생한다.

그 후에 다익스트라를 한번 더 돌리면 된다.

코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <numeric>

using namespace std;
using pii = pair<int, int>;

const int N = 505;
int dist[N];
bool visited[N];
bool check[N][N];
int n, m, s, e; 

vector<pii> adj[N];
vector<int> prv[N];

void dikstra() {
    priority_queue<pii, vector<pii>, greater<>> pq;
    fill(dist, dist + n, 1e8);
    pq.push({0, s});
    dist[s] = 0;
    while (!pq.empty()) {
        auto [d, cur] = pq.top();
        pq.pop();
        if (visited[cur]) continue;
        visited[cur] = true;
        for (const auto &[nxt, nd] : adj[cur]) {
            if (check[cur][nxt]) continue;
            int newD = dist[cur] + nd;
            if (dist[nxt] >= newD) {
                if (dist[nxt] > newD) prv[nxt].clear();
                dist[nxt] = newD;
                prv[nxt].push_back(cur);
                pq.push({dist[nxt], nxt});
            }
        }
    }
}

void dfs(int cur) {
    for (const auto &k : prv[cur]) {
    // 이미 없앤 경로는 다시 한번 없애지 않는다
    // 이 부분 없으면 재귀 호출이 많아져 시간초과 발생
        if (!check[k][cur]) dfs(k);
        check[k][cur] = true;
    }
}

void solve() {
    scanf("%d %d", &n, &m);
    if (!n && !m) exit(0);
    scanf("%d %d", &s, &e);
    while (m--) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({b, c});
    }
    dikstra();
    memset(visited, false, sizeof visited);
    dfs(e);
    dikstra();
 
    printf("%d\n", dist[e]  == 1e8 ? -1 : dist[e]);

    for (int i = 0; i < n; i++) {
        adj[i].clear();
        prv[i].clear();
        visited[i] = false;
        for (int j = 0; j < n; j++) check[i][j] = false;
    }
}

int main() {
    while (1) solve();
}