C++[백준]2307번 도로검문

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

2307번: 도로검문

 

솔루션

---

다익스트라의 응용 문제인 것 같다.

 

먼저 용의자가 갈 수 있는 가장 빠른 길을 다익스트라를 통해 찾아준다.

이 때, 값이 갱신될 때 마다 부모노드. 즉 어떤 노드에서 해당 노드로 왔는지 기록을 한다.

 

이렇게 다익스트라를 한 번 수행하면, 용의자가 이용하는 가장 빠른 경로를 찾을 수 있다.

 

경찰이 검문을 해야 하는 후보는 가장 빠른 경로중 하나이다.

 

경로 쌍을 방문하지 못하도록 조건문을 걸고, 도둑 입장에서 다익스타를 했을 때, 가장 큰 값이 나오면 해당 값으로 저장 하고 출력 해 주면 된다.

 

 

 

코드

---

#define INF 2100000000
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N, M;
vector<pair<int, int>> V[1002];
bool is_visit[1002][1001];
int parent[1002];
int dist[1002];

void dijkstra() {
	priority_queue<pair<int, int>> pq;
	
	dist[1] = 0;
	pq.push({ 0,1 });
	
	while (!pq.empty()) {
		int str = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();

		if (dist[str] < cost) continue;
		
		for (int i = 0; i < V[str].size(); i++) {
			int next = V[str][i].first;
			int val = V[str][i].second + cost;
			
			if (dist[next] > val && !is_visit[str][next]) {
				pq.push({ -val,next });
				dist[next] = val;
				parent[next] = str;
			}
		}
	}
}

void init(void) {
	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int a, b, t;
		cin >> a >> b >> t;
		V[a].push_back({ b,t });
		V[b].push_back({ a,t });
	}

	//검문이 없을 때, 최단 경로를 찾기.
	init();
	dijkstra();

	int d = dist[N];
	int str = N;
	//최단 경로를 가는 동안 방문하는 노드들의 쌍을 저장.
	queue<pair<int, int>> Q;
	while (str != 1) {
		Q.push({ str, parent[str] });
		str = parent[str];
	}


	int cnt = -INF;
	//각각의 노드 사이 간선을 이용 못하게 한다면.
	while (!Q.empty()) {
		int node1 = Q.front().first;
		int node2 = Q.front().second;
		Q.pop();
		
		is_visit[node1][node2] = true;
		is_visit[node2][node1] = true;
		init();
		dijkstra();
		is_visit[node1][node2] = false;
		is_visit[node2][node1] = false;
		cnt = max(cnt, dist[N]);
	}


	cout << (cnt == INF ? -1 : cnt - d) << "\n";

	return 0;	
}