[ BOJ 백준 5719번 - 거의 최단 경로 ] 해설 및 코드

https://www.acmicpc.net/problem/5719

 

목적

최단 경로를 모두 제거한 뒤에 최단 경로를 구하자.

 

접근법

1. 다익스트라 알고리즘으로 S에서 D로 가는 최단 경로를 구하자.

2. 그런다음 여러개가 될 수 있는 최단경로를 백트래킹으로 D부터 S까지 지워준다.

3. 이제 다시 최단 경로를 구하면 원하는 답이 나온다.

 

#include<bits/stdc++.h>
#define f(i,r,l) for(int i=r;i<l;++i)
using namespace std;
 
const int INF = 1e6;
int n, m, s, d, g[500][500], a[500];
 
struct edge {
    int v, p;
    bool operator<(const edge& oth)const { return p > oth.p; }
};
 
void dijkstra() {
    f(i, 0, n)a[i] = INF; a[s] = 0;
    priority_queue<edge> q; q.push({ s,0 });
    while (!q.empty()) {
        int p = q.top().p, v = q.top().v; q.pop();
        if (a[v] != p)continue;
        if (v == d)return;
        f(i, 0, n)if (g[v][i]) {
            int tmp = a[v] + g[v][i];
            if (a[i] > tmp) {
                a[i] = tmp;
                q.push({ i,tmp });
            }
        }
    }
}
 
void remove(int v) {
    f(i, 0, n)if (g[i][v] && a[i] + g[i][v] == a[v]) {
        g[i][v] = 0;
        remove(i);
    }
}
 
void solution() {
    memset(g, 0, sizeof(g));
    cin >> s >> d;
    while (m--) {
        int u, v, p; cin >> u >> v >> p;
        g[u][v] = p;
    }
 
    dijkstra();
    remove(d);
    dijkstra();
    cout << (a[d] == INF ? -1 : a[d]) << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    while (cin >> n >> m && n && m) solution();
    return 0;
}
 
 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.