백준 중량제한 1939(c++)

문제

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

설명

• 다익

• 파라메트릭 + bfs로 가능

• 그그그그 주어진 mid 값 가능한 최대 물건의 무게가 가능하냐 ? bfs(mid)

• 그렇다면 무게를 증가 시키자 s = mid + 1 , 아니라면 감소시키자 e = mid - 1

주의

• bfs(mid)가 true라면 가능한 값인데 다음에 다시 if(bfs(mid)) 가 무조건 걸린다는 확신이 없기에 여기에서 가능하다면 정답 값 ans에 mid값을 갱신을 해주어야한다.

• 매우 매우 잘못된 구간이 있었는데 그것은 반대로 생각한 것이다 mid값은 가능한 물건의 값인데 다리 무게로 코드 치다가 생각을 안해서 반대로 짰다 ㅠㅠㅠㅠ

• 그리고 bfs를 돌릴 때 쭉 돌리다가 마지막에 visitid[End]를 검사해서 도착여부를 보고 return을 해주어야한다.

소스

#include <bits/stdc++.h>

using namespace std;

int n, m, start, End;
// 4 * 4 => 14  
vector<pair<int, int>> Info[10001];
/*
vector가 10001개가 있다 
Info[now]를 하면 나온 것이 벡터이다 
*/
bool bfs(int &x) {

    int flagCost = x; // 해당 비용으로 가능한가 ? 
    bool visited[10001] = { false, };
    queue<int> q;
    q.push(start);
    visited[start] = 1;

    while (!q.empty())
    {
        int now = q.front(); q.pop();

        for (int i = 0; i < Info[now].size(); i++) {

            if (visited[Info[now][i].first]) continue; 

            int next = Info[now][i].first;
            int cost = Info[now][i].second;  // cost 다리가 버틸 수 있는 중량 

            if (flagCost <= cost) {  //  가능한 물건 무게  < 다리 무게
                q.push(next);
                visited[next] = 1;
            }                                                                    
        }
    }

    if (visited[End]) return true;
    else return false;
}

int main() {

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a = 0, b = 0, c = 0;; cin >> a >> b >> c;
        Info[a].push_back({ b, c });
        Info[b].push_back({ a, c });
    }

    cin >> start >> End;

    int s = 1, e = 1e9; // 범위 1 ~ 10억 

    int mid = 0;
    int ans = 0;

    while (s <= e)
    {
        mid = s + e >> 1;
        if (bfs(mid)) {
            s = mid + 1;
            ans = mid;
        }
        else {
            e = mid - 1;
        }
    }

    cout << ans;
    return 0;
}