1939번: 중량제한

문제링크: 1939번: 중량제한

문제

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

설명

다리의 하중을 의미하는 C의 범위가 1부터 1,000,000,000이므로 직감적으로 log C의 알고리즘을 사용해야하지 않을까라는 생각을 했다. 그래프와 시작섬, 도착섬이 주어졌으므로 도착섬까지는 BFS로 탐색이 가능하고 특정 하중에 대한 탐색을 YES, NO로 판별할 수 있다.

C에 대한 이분탐색으로 위 상황을 해결할 수 있는데 low를 edge의 최소값, high를 edge의 최대값으로 설정하고 mid를 limit으로 설정하고 시작섬에서 도착섬을 도착할 수 있는가를 따지면서 진행하면 문제를 해결할 수 있다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define endl '\n'

using namespace std;

int N, M;
vector<vector<pair<int, int>>> graph;

bool able(int limit, int start, int end) {
	vector<bool> check(N, false);

	queue<int> q;
	q.push(start);
	check[start] = true;
	while (!q.empty()) {
		int now = q.front();
		q.pop();

		if (now == end) return true;

		for (pair<int, int> p : graph[now]) {
			int next = p.first, cost = p.second;
			if (cost < limit || check[next]) continue;
			q.push(next);
			check[next] = true;
		}
	}
	return false;
}

void solve() {
	cin >> N >> M;
	graph.resize(N);

	int low = 1000000001, high = -1, mid;
	while (M--) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a - 1].push_back({ b-1,c });
		graph[b - 1].push_back({ a-1,c });
		low = min(low, c);
		high = max(high, c);
	}

	int start, end;
	cin >> start >> end;
	start -= 1; end -= 1;

	int ret = -1;
	while (low <= high) {
		mid = (low + high) / 2;
		if (able(mid, start, end)) {
			ret = mid;
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}
	cout << ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	//freopen("input.txt", "r", stdin);
	solve();
	return 0;
}