[BOJ 2325] 개코전쟁(c++)

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

 

문제 개요

n개의 정점과 m개의 간선이 있다. 간선 하나만 파괴하여 정점 1부터 정점 n까지의 최단거리가 가장 크게 만들 때 최단거리를 출력해야한다. 두 정점 사이의 간선은 두 개 이상 존재하지 않는다.

(1 <= n <= 1000)

(1 <= m <= n*n(-1)/2)

 

문제 풀이

 최단 거리 문제이기 때문에 다익스트라를 사용해 풀었다. 하나의 간선을 파괴하려면 최단거리의 경로 중의 한 간선을 파괴해야 한다. 왜냐하면 다른 간선을 파괴하면 최단거리에 영향을 주지 않기 때문인다. 최단거리를 구하면서 경로를 구하고, 그 경로에 있는 간선을 하나씩 무시하며 최단거리를 새로 구하며 비교하는 방식으로 구했다. 주의할 점은 간선을 지웠을 때 n까지 다다르지 못할 가능성이 있으므로 처음 경로를 구할 때의 최단거리 값을 넣어주어야 한다. 이렇게 하면 경로에 포함되지 않은 간선을 파괴한 것이다.

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int mx = 1e9;
vector<pair<int, int>> v[1001];
int dist[1001];
int path[1001];

void distInit(int n) {
	for (int i = 2; i <= n; i++) {
		dist[i] = mx;
	}
}

int makePath(int e) {
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, 1 });
	distInit(e);
	while (!pq.empty()) {
		int x = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if (x == e) return cost;
		for (int i = 0; i < v[x].size(); i++) {
			int y = v[x][i].first;
			int ncost = cost + v[x][i].second;
			if (dist[y] > ncost) {
				dist[y] = ncost;
				path[y] = x;
				pq.push({ -ncost, y });
			}
		}
	}
	return 0;
}

int dijkstra(int e, int px, int py) {
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, 1 });
	distInit(e);
	while (!pq.empty()) {
		int x = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if (e == x) return cost;
		for (int i = 0; i < v[x].size(); i++) {
			int y = v[x][i].first;
			int ncost = cost + v[x][i].second;
			if (x == px && y == py) continue;
			if (dist[y] > ncost) {
				dist[y] = ncost;
				pq.push({ -ncost, y });
			}
		}
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, res = 0;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, cost;
		cin >> x >> y >> cost;
		v[x].push_back({ y, cost });
		v[y].push_back({ x, cost });
	}
	res = makePath(n);
	for (int i = n; i != 1; i = path[i]) {
		res = max(res, dijkstra(n, path[i], i));
	}
	cout << res << '\n';
	return 0;
}