백준 5719 (C++) 거의 최단 경로

최초 업로드: 2025-09-06 19:47:36

최근 수정 시간: 2025-09-07 02:03:59

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] 거의 최단 경로

[문제 링크](https://www.acmicpc.net/problem/5719)

## 문제 설명

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다.

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

## 입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N) 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 103) 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다. U에서 V로 가는 도로는 최대 한 개이다. 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

## 출력

각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

## 풀이
첫번째 다익스트라로 최단 경로들을 찾고 역추적하며 모두 삭제하였고, 두번째 다익스트라로 다음 최단경로의 길이를 구하였다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX = 500;

int n, m, s, d;

struct edge {
    int u, v, c;
    bool operator==(const edge e) const {
        return u==e.u && v==e.v;
    }
};

vector<vector<edge>> conn, prv;

struct pos {
 int idx, val;
 bool operator<(const pos p) const {
 return val > p.val;
 }
};

int dijkstra() {
 vector<int> minCost(n, INF);
 prv = vector<vector<edge>>(n);
 priority_queue<pos> pq; pq.push({s, 0});
 minCost[s]=0;
 while(!pq.empty()) {
 pos cur = pq.top(); pq.pop();
 if(minCost[cur.idx] < cur.val || cur.idx==d) continue;

for(edge &next:conn[cur.idx]) {
            int nextCost = cur.val+next.c;
            if(minCost[next.v]>nextCost) {
                minCost[next.v] = nextCost;
                prv[next.v] = {next};
                pq.push({next.v, nextCost});
            } else if(minCost[next.v]==nextCost) {
                prv[next.v].push_back(next);
            }
        }
    }

vector<bool> visited(n);
 queue<int> q; q.push(d);
 visited[d]=true;
 while(!q.empty()) {
 int cur = q.front(); q.pop();
 if(cur==s) continue;
 prv[cur].erase(unique(prv[cur].begin(), prv[cur].end()), prv[cur].end());
 for(edge next:prv[cur]) {
 conn[next.u].erase(find(conn[next.u].begin(), conn[next.u].end(), next));
 if(!visited[next.u]) {
 visited[next.u]=true;
 q.push(next.u);
 }
 }
 }
 return (minCost[d] == INF ? -1 : minCost[d]);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 while(true) {
 cin >> n >> m >> s >> d;
 if(!n) break;
 conn = vector<vector<edge>>(n);
 while(m--) {
 int u, v, c; cin >> u >> v >> c;
 conn[u].push_back({u, v, c});
 }
 dijkstra();
 cout << dijkstra() << '\n';
 }
}
```