백준 1939

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

이 문제는 bfs에 이분탐색을 통한 적절한 값 찾기 이다 
처음에는 갈수있는 경로별 최댓값을 구하려 했으나 시간초과가 났다 당연한 얘기다

자 일단 이코드는 bfs를 통해 특정 노드에서 노드로 가는 경우의 수를 모두 탐색하는데 이때 우리는 무게를 계속 정해주고 해당 무게가 특정 다리의 cost를 넘어가면 이후 탐색의 값을 좀더 줄여 나가는 방식으로 진행한다 도착점에 도착하면 그이후로 탐색하지않는다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector < pair < int , int >> v[100001];
bool isVisited[100001];
int maxNum = 1000000000;
int bfs(int from, int to) {
	int lo = 1;
	int hi = maxNum;
	int mid;
	int ans;
	while (lo <= hi) {
		mid = (lo + hi) / 2;

		for (int i = 0; i < n+1; i++) {
			isVisited[i] = false;
		}

		queue<int> q;

		q.push(from);
		isVisited[from] = true;
		bool canMore = false;

		while (!q.empty()) {
			int node = q.front();
			q.pop();

			if (node == to) {
				canMore = true;
				break;
			}

			for (int i = 0; i < v[node].size(); i++) {
				int next = v[node][i].first;
				int cost = v[node][i].second;
				if (isVisited[next])
					continue;
				if (mid > cost)
					continue;
				isVisited[next] = true;
				q.push(next);
			}
		}

		if (canMore) {
			lo = mid + 1;
			ans = mid;
		}
		else {
			hi = mid - 1;
		}
	}
	return ans;

}
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	int a, b, c;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;

		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}

	int from, to;
	cin >> from >> to;
	int ans = bfs(from, to);
	cout << ans;

}