백준 5719번, 거의 최단 경로 / Almost Shortest Path

 

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

5719번: 거의 최단 경로

요약

 

정점 S에서 정점 D로 가는 최단경로에 포함되지 않은 도로로만 이루어진 그 다음 최단경로를 구한다.

---

1. 가중치가 존재하는 단방향 그래프가 주어진다.

 

2. 다익스트라를 통해 최단경로와 그 경로를 역추적하여 저장한다.

https://int-p.tistory.com/13

다익스트라(Dijkstra) 알고리즘과 최단경로 역추적

 

3. 2번에서 구한 최단경로에 포함된 간선을 전부 제거한다. 이때, 문제 조건에서 임의의 정점 U에서 V로 가는 도로가 최대 한 개이기 때문에, 최단경로에 포함된 두 정점간의 간선을 모두 제거해도 상관 없다.

 

4. 간선의 제거는 이미 존재하는 간선의 가중치를 INF로 변경하는 방식으로 진행하였다. 이때, 이미 제거된 간선이 또 제거되는 것을 방지하기 위해 방문 배열 mark[node]를 관리하며 DFS 형식으로 제거한다.

 

5. 간선의 개수가 최대 $10^{4}$이므로, 최단경로에 포함된 정점의 모든 간선을 검색하며 제거해도 1초 안에 처리 가능하다.

 

6. 간선이 제거된 그래프에서 다익스트라를 다시 한 번 돌려 거의 최대 경로를 구한다.

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;

struct cmp {
	bool operator() (pii A, pii B) {
		return A.first > B.first;
	}
};

int N, M, S, D;
vector <pii> graph[501];
int dist[501];
vector <int> path[501];
int mark[501];

void Dijkstra(int start);
void Delete_Path(int node);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	while (1) {
		cin >> N >> M;
		if (N == 0 && M == 0) break;
		cin >> S >> D;
		for (int i = 0; i < N; i++) {
			graph[i].clear();
			path[i].clear();
			mark[i] = 0;
		}
		for (int i = 0; i < M; i++) {
			int U, V, P;
			cin >> U >> V >> P;
			graph[U].push_back({ V,P });
		}
		Dijkstra(S);
		Delete_Path(D);
		Dijkstra(S);
		if (dist[D] == INF) cout << -1 << '\n';
		else cout << dist[D] << '\n';
	}
	return 0;
}

void Dijkstra(int start) {
	for (int i = 0; i < N; i++) dist[i] = INF;
	priority_queue<pii, vector<pii>, cmp> pq;
	pq.push({ 0, start });
	dist[start] = 0;
	while (pq.size()) {
		int now = pq.top().second;
		int val = pq.top().first;
		pq.pop();
		if (dist[now] < val) continue;
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int new_val = val + graph[now][i].second;
			if (dist[next] > new_val) {
				dist[next] = new_val;
				path[next].clear();
				path[next].push_back(now);
				pq.push({ new_val, next });
			}
			else if (dist[next] == new_val) path[next].push_back(now);
		}
	}
}

void Delete_Path(int node) {
	if (mark[node] != 0) return;
	mark[node] = 1;
	for (int i = 0; i < path[node].size(); i++) {
		int now = node;
		int prev = path[node][i];
		for (int j = 0; j < graph[prev].size(); j++) {
			if (graph[prev][j].first == now) graph[prev][j].second = INF; // 간선 제거			
		}
		Delete_Path(prev);
	}
}