백준 1939 중량제한

백준 1939 중량제한

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

문제

키 포인트

Parametric search 알고리즘을 이용해 물건의 중량을 can 함수에 대입하며 가능한 중량 중 최대 중량을 찾아낸다.

시행착오

bfs로 풀어보려고 했는데 시간초과로 포기.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define INF 1000000001
int n, m;
int from, to;
vector<pair<int,int>> link[100001];
bool vi[100001];
void init() {
	fill(vi, vi + n + 1, false);
}
bool can(int x, int from, int to) {
	if (from == to) return true;
	
	bool check = false;
	for (int i = 0; i < link[from].size(); i++) {
		if (link[from][i].first >= x && !vi[link[from][i].second]) {
			vi[link[from][i].second] = true;
			check = check || can(x, link[from][i].second, to);
		}
	}
	return check;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		link[a].push_back({ c,b });
		link[b].push_back({ c,a });
	}
	cin >> from >> to;

	int l = 1;
	int r = INF;

	while (l + 1 != r) {
		init();
		int mid = (l + r) / 2;
		if (can(mid, from, to)) l = mid;
		else r = mid;
	}
	cout << l;
}

추가

구현은 어렵지 않았는데 아직도 골드 수준 문제는 바로바로 풀이가 안떠오른다.ㅜㅜ