백준1939: 중량 제한

중량제한 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

24809

6454

4003

25.064%

문제

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인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

3 3
1 2 2
3 1 3
2 3 2
1 3

예제 출력 1 복사

3

 

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m;//섬 갯수 다리 갯수
int start, dest;
vector<pair<int,int>> graph[10001];
int visited[100001];
bool bfs(int mid) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (cur == dest)return true;

		for (int i = 0; i < graph[cur].size(); i++) {
			int nextCost = graph[cur][i].second;
			if (visited[graph[cur][i].first] == false && mid <= nextCost) {
				visited[graph[cur][i].first] = true;
				q.push(graph[cur][i].first);
			}
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	int from, to, weight;
	int max_weight=0;

	for (int i = 0; i < m; i++) {
		cin >> from >> to >> weight;
		graph[from].push_back({ to,weight });
		graph[to].push_back({ from,weight });
		max_weight = max(max_weight, weight);
	}

	cin >> start >> dest;

	int low = 0, high = max_weight;

	while (low <= high) {
		memset(visited, false, sizeof(visited));
		int mid = (low + high) / 2;
		if (bfs(mid))
			low = mid + 1;
		else
			high = mid - 1;
	}

	cout << high;
	return 0;
}

말그대로 이진 탐색을 통해서 최대값을 찾는다.