[1939] 중량제한

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

1939번: 중량제한

<문제>

양방향 그래프가 들어오고, 중량이 간선의 가중치보다 낮아야 이동이 가능할때 중량의 최대값을 구하는 문제다.

가능한 중량C가 1~10억이여서 중량 C에 대해서 이분탐색을 진행해주어야 한다.

bfs로 중량C에 대해서 정답의 가능성이 있는지를 판별한다. bool을 리턴하도록 구성해주었고

true가 리턴되면 중량C를 운송이 가능하다는 의미이므로 left=mid+1을 진행한다.

반대로 false가 리턴되면 중량을 줄여야하므로 right=mid-1을 진행한다.

가능한 경우 10억에 대해 이분탐색을 진행하니 log2(10억)번정도 bfs가 호출되겠다.

 

<소스코드>

#include<bits/stdc++.h>
using namespace std;
int n, m, s, e;
bool _visit[10001];
vector<pair<int, int>>adj[10001];
queue<int>q;
bool bfs(int w) {
    memset(_visit, false, sizeof(_visit));
    while (!q.empty())q.pop();
    q.push(s);
    _visit[s] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == e) {
            return true;
        }
        for (auto& x : adj[cur]) {
            if (x.second >= w && _visit[x.first] == false) {
                q.push(x.first);
                _visit[x.first] = true;
            }
        }
    }
    return false;
}
int main(void) {
    int i, left = 0, right = 0;
    scanf("%d %d", &n, &m);
    for (i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        right = max(z, right);
        adj[x].push_back({ y,z });
        adj[y].push_back({ x,z });
    }
    scanf("%d %d", &s, &e);
    while (left <= right) {
        int mid = (left + right) / 2;
        if (bfs(mid) == true)left = mid + 1;
        else right = mid - 1;
    }
    printf("%d", right);
    return 0;
}