[BOJ 1939] 중량제한

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

주어진 도로의 중량제한을 넘어서지 않는 배달가능한 최대물품중량을 계산하는문제이다.

BFS와 이분탐색을 이용해서 문제를 해결하면 된다. 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <stdio.h>
 
#define INF 1e9
typedef long long ll;
using namespace std;
 
int n,m,mid,dist[111111],s,e;
bool visit[111111];
vector<vector<pair<int,int>>> v;
 
bool solve(){
    queue<int> q;
    q.push(s);
    
    while(!q.empty()){
        int t = q.front();
        if(t == e){
            return true;
        }
        q.pop();
        if(visit[t])continue;
        visit[t] = true;
        
        for(int i=0;i<v[t].size();i++){
            int cost = v[t][i].second;
            int next = v[t][i].first;
            if(cost >= mid){
                q.push(next);
            }
        }
    }
    return false;
}
 
int main(){
    cin >> n >>m;
    v.resize(n+1);
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >>c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    cin >>s >>e;
    
    int l = 1;
    int r = 10000000;
    int ans =0;
    while(l<=r){
        memset(visit,false,sizeof(visit));
        mid = (r+l)/2;
        cout << l << " " << r << " " <<mid;
        if(solve()){
            cout << "can" <<endl;
            ans = mid;
            l = mid+1;
        }else{
            cout << "false" <<endl;
            r = mid-1;
        }
        
    }
    cout << ans <<endl;
    return 0;
}