[BS] 백준 1939 중량제한

백준 강의 코드.

이분탐색 쉬운 것 같다. 

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <cstring>

#include <stack>

#include <queue>

#include <limits.h>

#include <map>

#include <stdlib.h>

using namespace std;

typedef unsigned long long ull;

typedef long long ll;

int n,m,st,endd;

int tb1[100001];

int tb2[1001][1001];

int che2[1001][1001];

ull che1[100001];

string s[100001];

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

bool visited[10001];

bool dfs(int idx, int limit){

    if(visited[idx]){

        return false;

    }

    visited[idx] = true;

    if(idx == endd) {

        return true;

    }

    for(int i=0;i<a[idx].size();++i){

        int next = a[idx][i].first;

        int cost = a[idx][i].second;

        if(cost >= limit){

            if(dfs(next, limit)){

                return true;

            }

        }

    }

    return false;

}

int main(void){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cin >> n >> m;

    for(int i=0;i<m;++i){

        int x,y,z;

        cin >> x >> y >> z;

        a[x].push_back(make_pair(y,z));

        a[y].push_back(make_pair(x,z));

    }

    cin >> st >> endd;

    int left, right;

    left = 1;

    right = 1000000000;

    int ans = 0;

    while(left <= right){

        // cout << "left : " << left << endl;

        // cout << "rt : " << right << endl;

        int mid = left + (right - left) / 2;

        memset(visited, false, sizeof(visited));

        if(dfs(st,mid)){    

            ans = mid;

            left = mid + 1;

        }

        else{

            right = mid - 1;

        }

    }

    cout << ans << endl;

    return 0;

}