[1939] 중량제한

### Parametric Search + BFS ###

[1939] 중량제한 : http://boj.kr/1939

<소스코드>

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
struct P { int to, limit; };
 
int n, m;
int a, b, c;
vector<P> v[10001];
 
bool isPossible(int mid)
{
 
    queue<int> q;    
    q.push(a);
    
    vector<bool> visited(n+1, 0);
    visited[a] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
 
        for(auto &p : v[cur]) {
            int next = p.to;
            int c = p.limit;
            if(!visited[next] && mid <= c) {
                if(next == b) return true;
                q.push(next);
                visited[next] = 1;
            }
        }
    }
    return false;
}
 
int main()
{
    scanf("%d%d", &n, &m);
 
    while(m--) {
        scanf("%d%d%d", &a, &b, &c);
        v[a].push_back((P){b, c});
        v[b].push_back((P){a, c});
    }
 
    scanf("%d%d", &a, &b);
    
    int s=1, e=1e9;
    while(s <= e) {
        int mid = (s+e)/2;
        if(isPossible(mid)) s = mid+1;
        else e = mid-1;
    }
    printf("%d\n", s-1); 
    return 0;
}
 

>> 중량을 mid 로 설정했을 때, 이게 답이 될 수 있으면 탐색범위를 [mid+1, e] 로 좁혀간다. 

>> 답이될 수 없다면 [s, mid-1] 로 좁힌다.