[BOJ/Platinum 5] 백준 2325 개코전쟁(C++)

문제 링크

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

2325번: 개코전쟁

 

문제

“앙두레 강”이 개미와 코끼리 결혼식에서 기차를 아름답게 만드는 것을 실패했기 때문에 식장이 아수라장이 되고 결혼이 물거품이 되어버렸다. 급기야는 왕국 간에 분쟁으로 이어져 개미왕국은 코끼리왕국을 공격하기로 결정하였다. 동물나라 지도에서 개미왕국은 1번 정점에 위치해 있고 코끼리왕국은 N번 정점에 위치해 있다. 따라서 개미왕국이 1번 정점에서 N번 정점으로 공격을 하러 가는 상황이다. (개미왕국은 최단거리로 이동을 하게 되고, 코끼리왕국은 움직이지 않는다)

“개미”와 “코끼리”의 앞 글자를 따서 이 전쟁은 “개코전쟁”으로 역사에 기억된다.

“앙두레 강”은 자신 때문에 발생한 이 전쟁을 어떻게든 막으려고 한다. 협상을 할 시간을 벌기 위해 개미왕국이 코끼리왕국에 도착하는 시간을 최대한 늦추려고 한다. 그래서 “앙두레 강”은 사자왕국의 도움을 빌어 도로 중 딱 하나를 파괴하려고 하는데 어느 도로를 파괴해야 개미왕국이 최단거리로 가더라도 그 거리를 최대로 할 수 있을까?

“앙두레 강”를 도와 1번 정점에서 N번 정점으로의 최단거리가 최대가 되도록 도로 하나를 파괴하도록 하자. (어떤 하나의 도로를 파괴하더라도 1번 정점에서 N번 정점으로 도달 가능하다)

입력

첫 줄에 N과 M이 입력된다. N은 정점의 개수이고 M은 도로의 수이다. (1 ≤ N ≤ 1000, 1 ≤ M ≤ N×(N-1)/2)

다음 줄부터 M개의 줄에 도로의 정보가 입력된다.

i+1번째 줄에는 i번째 도로의 정보 xi yi zi가 입력되고 이 도로는 정점 xi와 정점 yi를 잇는 도로이며 지나는데 zi만큼의 시간이 걸린다는 것을 의미한다. 두 정점사이에는 두 개 이상의 길이 존재하지 않고 모든 도로는 양방향이며 한 도로를 파괴하는 것은 양방향의 길 모두를 파괴하는 것이다. (1 ≤ xi, yi ≤ N, 1 ≤ zi ≤ 1000)

출력

적당한 도로하나를 파괴했을 때 1번 정점에서 N번 정점으로의 최단거리의 최댓값을 출력한다.

예제 입력 1

5 6
1 2 4
1 3 3
2 3 1
2 4 4
2 5 7
4 5 1

예제 출력 1

11

예제 입력 2

6 7
1 2 1
2 3 4
3 4 4
4 6 4
1 5 5
2 5 2
5 6 5

예제 출력 2

13

예제 입력 3

5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10

예제 출력 3

27

알고리즘 분류

• 최단 거리 알고리즘

풀이

처음 다익스트라를 수행하면서 최단 경로를 기록한다. (Prev[nextX] = CurX : nextX의 이전 정점이 CurX라는 의미)

그리고 경로의 마지막 도로부터 처음 도로까지 순차적으로 막으면서 다익스트라를 수행하면서 최단 거리의 최댓값을 구해준다.

최단 경로에 해당하는 도로만을 막는 이유는, 만약 최단 경로에 해당하지 않는 도로를 막을 경우 최단 경로를 따라서 이동하기 때문에 그대로 최단 거리가 나오게 된다. 그렇게 모든 도로를 막으면서 다익스트라를 수행하면 시간 제한에 걸리게 된다. 따라서 최단 경로에 해당하는 도로만을 막아 줘야 최단 거리보다 큰 값을 구할 수 있다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
vector<pair<int, int> > Edge[MAX];
int Cost[MAX];
int Prev[MAX];
int answer;

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

void Input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int X, Y, Z;
		cin >> X >> Y >> Z;
		Edge[X].push_back(make_pair(Y, Z));
		Edge[Y].push_back(make_pair(X, Z));
	}
}

void Dijkstra(int X) {
	priority_queue<pair<int, int> > PQ;
	Cost[1] = 0;
	PQ.push(make_pair(0, 1));

	while (!PQ.empty()) {
		int CurC = -PQ.top().first;
		int CurX = PQ.top().second;
		PQ.pop();

		if (Cost[CurX] < CurC) {
			continue;
		}

		for (int i = 0; i < Edge[CurX].size(); i++) {
			int nextC = Edge[CurX][i].second;
			int nextX = Edge[CurX][i].first;
			if (((CurX == Prev[X]) && (nextX == X)) || ((CurX == X) && (nextX == Prev[X]))) {
				continue;
			}
			if (Cost[nextX] > CurC + nextC) {
				Cost[nextX] = CurC + nextC;
				if (X == 0) {
					Prev[nextX] = CurX;
				}
				PQ.push(make_pair(-Cost[nextX], nextX));
			}
		}
	};
}

void Find_Answer() {
	Init();
	Dijkstra(0);
	answer = Cost[N];
	for (int i = N; i > 1;) {
		Init();
		Dijkstra(i);
		i = Prev[i];
		answer = max(answer, Cost[N]);
	}
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}