백준 2307번, 도로검문

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

2307번: 도로검문

요약

 

간선 하나를 제거하여 1번 정점에서 N번 정점으로 가는 최단경로를 최대로 만든다.

---

1. 도시의 주요 지점 N개와 도로 M개로 이루어진 가중치 무방향 그래프가 주어진다.

 

2. 우선, 지연시킬 수 있는 최대 시간은 (간선 제거 후 최단경로) - (간선 제거 전 최단경로)이므로, 다익스트라를 통해 간선 제거 전 최단경로를 구한다.

 

3. 간선을 하나 제거하여 최단경로를 변경시키기 위해서는 제거하는 간선이 최단경로에 포함되어야만 한다. 따라서 2번 과정에서 최단경로 역추적을 같이 진행한다.

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

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

 

4. DFS로 최단경로를 탐색하며 최단경로에 포함된 모든 간선을 candidate 배열에 넣어준다.

 

5. 브루트포스 기법을 사용하여 candidate 배열의 모든 간선을 하나씩 제거하며 답을 구할 수 있다.

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

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

int N, M, org, ans;
vector <pii> graph[1001];
vector <int> path[1001];
vector <pii> candidate;
int dist[1001];
int mark[1001];
int blocked[1001][1001];

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int A, B, T;
		cin >> A >> B >> T;
		graph[A].push_back({ B,T });
		graph[B].push_back({ A,T });
	}
	Dijkstra(1);
	org = dist[N];
	MakeCandidate(N);
	for (int i = 0; i < candidate.size(); i++) {
		blocked[candidate[i].first][candidate[i].second] = 1;
		blocked[candidate[i].second][candidate[i].first] = 1;
		Dijkstra(1);
		ans = max(ans, dist[N]);
		blocked[candidate[i].first][candidate[i].second] = 0;
		blocked[candidate[i].second][candidate[i].first] = 0;
	}
	if (ans == INF) cout << -1;
	else cout << ans - org;
	return 0;
}

void Dijkstra(int start) {
	for (int i = 1; i <= N; i++) dist[i] = INF;
	priority_queue <pii, vector<pii>, cmp> pq;
	dist[start] = 0;
	pq.push({ 0,start });
	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;
			if (blocked[now][next] == 1) continue; // 검문중인 도로
			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 });
			}
			if (dist[next] == new_val) path[next].push_back(now);
		}
	}
}

void MakeCandidate(int node) {
	if (mark[node] != 0) return;
	if (node == 1) return;
	mark[node] = 1;
	for (int i = 0; i < path[node].size(); i++) {
		candidate.push_back({ node, path[node][i] });
		MakeCandidate(path[node][i]);
	}
}