[백준 2307] 도로검문

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

2307번: 도로검문

#include <cstdio>
#include <queue>
#include <list>
int N, M;
struct _st
{
	int n;
	int t;
};
std::list<_st> L[1000 + 2];

struct COMP
{
	bool operator()(const _st &a, const _st &b) {
		return a.t > b.t;
	}

};
std::priority_queue<_st, std::vector<_st>, COMP> PQ;
int visited[1000 + 2];
int route[1000 + 2];

void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int a = 0, b = 0, t = 0;
		scanf("%d %d %d", &a, &b, &t);
		L[a].push_back({ b, t });
		L[b].push_back({ a, t });
	}
}


int no_chk()
{
	// init
	PQ = {};
	for (int i = 1; i <= N; i++) {
		visited[i] = 0x7fffffff;
		route[i] = -1;
	}

	PQ.push({ 1, 0 });
	visited[1] = 0;
	route[1] = -1;

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		if (data.n == N) return visited[N];

		for (_st next : L[data.n]) {
			if (visited[next.n] <= visited[data.n] + next.t) continue;
			visited[next.n] = visited[data.n] + next.t;
			PQ.push({ next.n, visited[next.n] });
			route[next.n] = data.n;
		}
	}
}


int chk(int u, int v)	
{
	// init
	PQ = {};
	for (int i = 1; i <= N; i++) {
		visited[i] = 0x7fffffff;
	}

	PQ.push({ 1, 0 });
	visited[1] = 0;

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		if (data.n == N) return visited[N];

		for (_st next : L[data.n]) {
			if (visited[next.n] <= visited[data.n] + next.t) continue;
			if (data.n == u && next.n == v) continue;
			if (data.n == v && next.n == u) continue;
			visited[next.n] = visited[data.n] + next.t;
			PQ.push({ next.n, visited[next.n] });
		}
	}
	return -1;
}




int choose_edge() 
{
	int max_time = 0;
	for (int i = 1; i <= N; i++) {
		if (route[i] == -1) continue;
		int res = chk(route[i], i);	// u -> v, v -> u를 막는다  
		if (res == -1) return -1;
		if (res > max_time) max_time = res;
	}
	return max_time;
}



int main()
{
	input();
	int time1 = no_chk();
	//printf("%d", time1);
	int time2 = choose_edge();
	if (time2 == -1) printf("%d\n", -1);
	else printf("%d\n", time2 - time1);
	return 0;
}

원래는 인풋받은 모든 간선에 대하여 하나하나 검문을 해주는 코드를 작성했다. AC는 받았지만 실행시간이 1000ms나 되어 세상에서 제일 비효율적인 코드라는 생각에 공부 좀 하고 옴.. 

 

이 문제는 모든 간선에 대하여 검문을 할 필요가 없다. 

용의자가 최소 시간으로 N 에 도달하도록 하는 경로들 중에서 하나를 막았을 때, 얼마나 시간이 지연되는지 계산해주면 된다. 

따라서 경로를 저장하기 위해 route라는 배열을 선언하고, -1로 초기화 해주었다. 만약 어떤 노드의 valuer가 -1이면 최소 시간으로 이동할 때, 해당 노드를 지나가지 않는다는 뜻이다. 

route의 인덱스는 다음 노드 번호이고, route의 value는 현재 노드 번호이다. 

 

이러한 처리 후 choose_edge에서 간선을 선택해줄 때는, 용의자가 지나가지 않는 간선을 검문하더라도 시간의 변화에는 아무 영향이 없으므로 continue한다. 용의자가 지나가는 간선에 대해서만 BFS 함수를 실행하여 N까지 도달하는데 걸리는 시간을 계산해주면 된다.