5719번: 거의 최단 경로
문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만
www.acmicpc.net
- 최단경로를 찾아 포함된 간선을 모두 제거해야 한다.
- 따라서 삭제가 O(2 * N)인 벡터 기반 인접 리스트 (x)
- 삭제가 O(1)인 인접 행렬 (o)
- 대신 다익스트라에서 u와 인접한 v를 찾는 연산이
- (u와 인접한 정점 개수)에서 |V|로 증가한다.
- 인접행렬 cst[|V|][|V|]
- inf = |V| * max(weight) = 500 * 1000 = 500000
- cst[u][v]값이 inf이면 두 정점은 연결되지 않았다.
- cst[u][v]값이 inf가 아니면 그 값은 두 정점을 연결하는 비용
- S에서 D로 가는 모든 최단 경로
- 최단거리가 갱신될 때 부모를 갱신하는 방법으로는 가장 처음으로 발견한 최단경로만 구할 수 있다.
- 최단 거리 구하기 2 참조. 이 문제가 스페셜 저지인 이유도 '처음으로 발견한' 최단경로는 다익스트라 구현에 따라 달라질 수 있기 때문 -> 최단경로 중 어느 것을 출력하든지 AC
- 부모 배열을 벡터로 선언하여 최단 거리가 여러개일 경우 모든 부모를 저장할 수 있도록 변경
- 부모 자료구조를 재귀로 트리 순회하여 모든 최단 경로의 간선 제거 가능
- u와 v를 잇는 간선 제거는 cst[u][v]에 inf를 할당하기
- 최단거리가 갱신될 때 부모를 갱신하는 방법으로는 가장 처음으로 발견한 최단경로만 구할 수 있다.
/* 1. vertex 인덱스 0부터 시작 */
/* 2. 최단거리가 여러개일 경우 최단거리가 존재하지 않을 때까지 포함된 도로를 제거한다 */
/* 2. ㄴ 다익스트라로는 가장 처음으로 발견한 최단경로만 갱신된다. */
/* 최단경로를 단축시키지 못하더라도 동일한 길이의 최단경로라면 여러개의 부모를 갱신할 수 있도록하여 트리 형성 */
/* 브루트포스로 이 트리를 순회하여 최단경로에 포함된 도로를 모두 제거한다 */
/* 3. adj list에서 adj matrix로 변경하는 과정에서 양방향 그래프로 바꿔버림 -> 단방향으로 수정하기 */
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M, S, D;
int cst[500][500]; // 초기화 완료 /* 1 */
int inf = 500000;
int dist[500];
vector<int> prnt[500]; // 초기화 완료
void bf(int v) {
if (prnt[v].empty()) { // 부모가 없는 노드는 S이므로 재귀를 중지한다.
return;
}
for (auto u : prnt[v]) {
cst[u][v] = inf;
bf(u);
}
}
void dijkstra() {
fill(dist, dist + N, inf);
dist[S] = 0;
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, S));
while (!pq.empty()) {
int P = -pq.top().first, U = pq.top().second;
pq.pop();
if (dist[U] < P) continue;
for (int V = 0; V < N; ++V) {
if (cst[U][V] == inf) continue;
if (dist[U] + cst[U][V] > dist[V]) continue;
if (dist[U] + cst[U][V] == dist[V]) {
prnt[V].push_back(U);
continue;
}
prnt[V].clear();
prnt[V].push_back(U);
dist[V] = dist[U] + cst[U][V];
pq.push(make_pair(-dist[V], V));
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
while (1) {
cin >> N >> M;
if (N == 0) {
break;
}
for (int U = 0; U < N; ++U) {
fill(cst[U], cst[U] + N, inf);
}
cin >> S >> D;
while (M--) {
int U, V, P;
cin >> U >> V >> P;
cst[U][V] = P; /* 3 */
}
// 최단 경로 제외
dijkstra();
prnt[S].clear();
bf(D);
// 거의 최단 경로
dijkstra();
if (dist[D] == inf) {
cout << -1 << '\n';
}
else {
cout << dist[D] << '\n';
}
}
return 0;
}