백준 1939번: 중량제한 - Parametric Search, BFS

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

1939번: 중량제한

#include <bits/stdc++.h>
using namespace std;


int n, m;
int startIsland, endIsland;

vector<pair<int, int> > adj[10001];

bool BFS(int st, int en, int weight){
    bool vis[10001];
    memset(vis, 0, sizeof(vis));
    queue<int> Q;

    Q.push(st); vis[st] = 1;
    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        if(cur == en){
            return true;
        }

        for(auto nx : adj[cur]){
            if(!vis[nx.first]&&nx.second >= weight){
                vis[nx.first] = 1; Q.push(nx.first);
            }
        }
    }
    return false;
}



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;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    cin >> startIsland >> endIsland;


    //이분탐색
    int st = 1, en = 1000000000;

    while(st <= en){
        int mid = (st+en)/2;
        if(BFS(startIsland, endIsland, mid)){
            st = mid+1;
        }
        else{
            en = mid-1;
        }
    }

    cout << en << '\n';

    return 0;
}