중량제한

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
 
int n, m;
int sx, fx;
vector<pair<int, int> > v[10001];
bool d[10001];
 
bool bfs(int value) {
    queue<int> q;
    q.push(sx);
    d[sx] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (x == fx) return true;
        for (int i = 0; i < v[x].size(); i++) {
            int next = v[x][i].first;
            int nv = v[x][i].second;
            if (!d[next] && value <= nv) {
                d[next] = true;
                q.push(next);
            }
        }
    }
    return false;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    int maxx = 0;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
        maxx = max(maxx, c);
    }
 
    cin >> sx >> fx;
    int L = 0; int R = maxx;
    while (L <= R) {
        
        int mid = (L + R) / 2;
        if (bfs(mid)) {
            L = mid + 1;
        }
        else {
            R = mid - 1;
        }
        for (int i = 1; i <= n; i++)
            d[i] = false;
        
    }
    cout << R << '\n';
    return 0;
}

BFS를 통한 확인 -> 이분탐색하기문제

쉬운문제는 아니다 여러번 틀렸었고

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
 
using namespace std;
 
vector<pair<int, long>> v[10001];
bool d[10001];
long long dist[10001];
int n, m;
int sx, ex, ans;
 
void bfs(int x) {
    queue<pair<int, int> > q;
    d[x] = true;
    for (int i = 0; i < v[x].size(); i++) {
        q.push({ v[x][i].first, v[x][i].second });
        d[v[x][i].first] = true;
        dist[v[x][i].first] = v[x][i].second;
 
    }
    while (!q.empty()) {
        x = q.front().first; int val = q.front().second;q.pop();
        if (x == ex) {
            if (val > ans) {
                ans = val;
                continue;
                //cout << val << '\n';
            }
        }
        if (val <= ans  || dist[x] <= ans)
            continue;
        for (int i = 0; i < v[x].size(); i++) {
            //if (v[x][i].second < val) continue;
            if (d[v[x][i].first] == false) {
                d[v[x][i].first] = true;
                if (v[x][i].second < val) {
                    q.push({ v[x][i].first , v[x][i].second });
                    dist[v[x][i].first] = v[x][i].second;
                }
                else {
                    q.push({ v[x][i].first, val });
                    dist[v[x][i].first] = val;
                }
            }
            else {
                if (dist[v[x][i].first] < val && v[x][i].second > dist[v[x][i].first]) {
                    if (v[x][i].second > val) {
                        q.push({ v[x][i].first, val });
                        dist[v[x][i].first] = val;
                    }
                    else {
                        q.push({ v[x][i].first, v[x][i].second });
                        dist[v[x][i].first] = v[x][i].second;
                    }
                }
            }
        }
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b; long long c;
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
    }
 
    cin >> sx >> ex;
    bfs(sx);
    cout << ans << '\n';
    return 0;
}

다음같이 순수 BFS로 짜게되면 경우의수가 너무많아진다. 돌았던곳을 여러번 돌아야하는것은 효율적이지 못하고

이를 최대한 제거하면서 할수있는게, 출발 노드로부터 반개이상의 노드의 값들을 확인하면서 진행하는

이분탐색이 해당문제풀이에 알맞다