[백준] 5719 거의 최단 경로
January 06, 2021
문제 링크
알고리즘
다익스트라, dfs 또는 bfs
풀이
최단 경로는 다익스트라를 이용해 쉽게 풀 수 있다. 하지만 이 문제에서 거의 최단 경로란 “최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것”을 의미한다. 그리고 한 장소에서 다른 장소로 가는 도로는 최대 한 개이다.
- 단방향 그래프를 인접 행렬로 표현하되, 간선이 없는 경우 -1로 초기화한다. 인접 리스트가 아닌 인접 행렬로 표현하면 간선 삭제에 용이하다.
-
다익스트라를 통해 최단 경로를 구해가며
trace에 어느 정점에서 왔는지 기록을 남긴다.- 단, 최단 거리가 갱신될 때마다 해당 정점의 기록을 삭제한다.
- 최단 거리가 여러 개일 수 있으므로 거리가 같을 때도 기록을 해야 한다.
- 도착점으로부터 dfs 또는 bfs를 통해 간선을 없앤다.
- 이제 다시 다익스트라를 통해 최단 거리를 구하면 거의 최단 거리를 구할 수 있다.
- 시간 복잡도는
코드
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
const int MAX = 500;
const int INF = 987654321;
vector<int> trace[MAX];
int g[MAX][MAX];
int n, m, s, d;
vector<int> dijkstra() {
vector<int> dist(n, INF);
priority_queue<pii, vector<pii>, greater<>> pq;
dist[s] = 0;
pq.push({dist[s], s});
while (!pq.empty()) {
int d = pq.top().first;
int cur = pq.top().second;
pq.pop();
if (dist[cur] < d) continue;
for (int next = 0; next < n; next++) {
if (g[cur][next] == -1) continue;
int nd = d + g[cur][next];
if (nd < dist[next]) {
dist[next] = nd;
pq.push({dist[next], next});
trace[next].clear();
}
if (nd <= dist[next]) {
trace[next].push_back(cur);
}
}
}
return dist;
}
void removeShortestPath(int v) {
for (auto u : trace[v]) {
if (g[u][v] == -1) continue;
g[u][v] = -1;
removeShortestPath(u);
}
}
int main() {
while (1) {
for (int i = 0; i < MAX; i++) {
memset(g[i], -1, sizeof(g[i]));
trace[i].clear();
}
scanf("%d %d", &n, &m);
if (n == 0 && m == 0) {
break;
}
scanf("%d %d", &s, &d);
for (int i = 0, u, v, p; i < m; i++) {
scanf("%d %d %d", &u, &v, &p);
g[u][v] = p;
}
dijkstra();
removeShortestPath(d);
vector<int> dist = dijkstra();
printf("%d\n", dist[d] == INF ? -1 : dist[d]);
}
return 0;
}