1939 중량제한

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

정답(최대 중량제한)의 범위를 이분 탐색으로 줄여나가면서 최종 정답을 찾는다. BFS를 이용하여 답으로 정한 중량제한으로 시작점에서 도착점으로 갈 수 있는지 확인한다. 갈 수 있다면 범위를 올리면서 최대치를 찾고 갈 수 없다면 범위를 내린다.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
vector<pair<int,int>> a[100001];
int n,m,u,v,w,s,e;
 
bool bfs(int w)
{
    queue<int> q;
    vector<bool> visit(n+1,false);
    visit[s]=true;
    q.push(s);
    while(!q.empty())
    {
        int now=q.front(); q.pop();
        for(auto i : a[now])
        {
            int next=i.first,weight=i.second;
            if(visit[next] || weight<w) continue;
            if(next==e) return true;
            visit[next]=true,q.push(next);
        }
    }
    return false;
}
 
void bs()
{
    int left=0,right=1000000000,mid,ans=0;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(bfs(mid))
        {
            if(ans<mid) ans=mid;
            left=mid+1;
        }
        else right=mid-1;
    }
    printf("%d\n",ans);
}
 
int main()
{
    scanf("%d %d",&n,&m);
    while(m--)
    {
        scanf("%d %d %d",&u,&v,&w);
        a[u].push_back({v,w});
        a[v].push_back({u,w});
    }
    scanf("%d %d",&s,&e);
    bs();
    return 0;
}