[백준 1939] 중량제한, C++

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

1939번: 중량제한

 본 문제는 두 개의 섬에 다리를 세워 물품을 수송하려고 한다. 그런데 각각의 다리마다 중량 제한이 있다. 중량 제한을 초과하면 다리를 통과할 수 없다. 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 문제다. 문제 해결 순서는

1. 섬을 연결하는 다리와 중량제한을 인접 리스트에 저장한다.
2. 무게를 정하고 다리를 지나가 본다.
3. 지날 수 있는 무게의 최댓값을 구한다.

이때, 2번 조건에서 무게를 정할 때, 이분 탐색을 이용해서 풀 수 있다.

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
vector<pair<int, int>> v[10001];
bool chk[10001];
int Start, End;
int ans;
bool bfs(int Start, int Lim) {
    queue<int> q;
    chk[Start] = true;
    q.push(Start);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        if (node == End) {
            ans = Lim;
            return true;
        }
        for (int k = 0; k < v[node].size(); k++) {
            int next = v[node][k].first;
            int cost = v[node][k].second;
            if (cost >= Lim && !chk[next]) {
                chk[next] = true;
                q.push(next);
            }
        }
    }
    return false;
}
 
void cal(int left, int right) {
    if (left > right) return;
    int mid = (right + left) / 2;
    memset(chk, false, sizeof(chk));
    if (bfs(Start, mid)) cal(mid+1, right);
    else cal(left, mid-1);
}
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        // 인접 리스트에 저장
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));
    }
    scanf("%d %d", &Start, &End);
    // 이분 탐색
    cal(1, 1000000000);
    printf("%d\n", ans);
}