[baekjoon 2307] 도로검문 (다익스트라) (C++)

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

2307번: 도로검문

 

용의자가 주어진 그래프를 빠져나가려는데, 그래프 중 하나의 간선을 막아서 얼마나 지연시킬 수 있는지 출력하는 문제이다.

 

구역은 최대 1000개, 간선의 개수는 최대 5000개가 주어진다.

 

따라서 완전 탐색으로 모든 도로를 지우며 비교하는 것은 시간 초과가 날 것이다.

 

우선 1번부터 N번까지 최단 거리를 구해야 하므로 다익스트라를 이용하고, 최단 거리가 나오는 경로를 구해서 그 경로에 해당하는 도로만 지우면서 비교를 해주면 되겠다는 생각이 들었다.

 

따라서 첫 다익스트라를 돌려서 최단 경로를 구하고, 그 경로에서 도로를 하나씩 지우면서 다익스트라를 돌리며 늘어난 최단 거리의 차이점을 출력하거나, 도로를 지워서 아예 도착을 못하는 경우는 -1을 출력한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#define INF 987654321

using namespace std;

typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii>> pq;

int n, m, dis[1001], from, to, weight, parent[1001];
vector<pii> v[1001], path;
pii check; // 도로를 지우기 위한 x,y pair

bool pathCheck(int x, int y) { // 막힌 도로에 해당하는 간선인지 체크
	if ((x == check.first || x == check.second) && (y == check.first || y == check.second))
		return true;
	return false;
}

void dijkstra(int startX) {
	dis[startX] = 0;
	pq.push(make_pair(0, startX));

	while (!pq.empty()) {
		int x = pq.top().second;
		int disSum = pq.top().first;
		pq.pop();

		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i].first;
			int weight = v[x][i].second;

			if (pathCheck(x, nx)) // 막힌 도로면 패스
				continue;

			if (dis[nx] > disSum + weight ) {
				dis[nx] = disSum + weight;
				pq.push(make_pair(dis[nx], nx));
				parent[nx] = x; // 최단 경로를 위해 저장해준다.
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> weight;
		v[from].push_back(make_pair(to, weight));
		v[to].push_back(make_pair(from, weight));
	}

	for (int i = 1; i <= n; i++) {
		dis[i] = INF;
	}
	dijkstra(1);

	stack<int> st;

	for (int i = n; i != 1; i = parent[i])
		st.push(i);

	int from = 1;
	int to = 0;
	while (!st.empty()) {
		to = st.top();
		st.pop();
		path.push_back(make_pair(from, to));
		from = to;
	} // 거꾸로 스택에 저장된 경로를 저장해준다.
    // 9 5 3 1 이면 1-3, 3-5, 5-9
	
	int normalAnswer = dis[n]; // 첫 다익스트라 값
	int pendingAnswer = 0;

	for (auto k : path) {
		check.first = k.first;
		check.second = k.second; // 도로 하나 삭제
		for (int i = 1; i <= n; i++) { // 다익스트라 거리 배열 초기화
			dis[i] = INF;
		}
		dijkstra(1);
		if (dis[n] == INF) { // 도로를 막아서 도착하지 못하면 -1 출력 후 종료
			cout << -1;
			return 0;
		}
		else {
			pendingAnswer = max(pendingAnswer, dis[n]); // 지연된 거리의 최대값을 저장
		}
	}
	cout << pendingAnswer - normalAnswer; // 차이값을 출력
	return 0;
}