Cerința

Porumbeii au pornit un război crâncen împotriva ciorilor, dar ele au construit garduri defensive pe toate rutele pe care le-ar putea folosi armata porumbeilor pentru a le ataca cetatea. Pentru a ajunge la cetatea ciorilor armata trebuie sa treacă de gardurile construite de ciori.

Exemplu

Ohoo.in

5 6
1 2 3
1 4 1
2 3 2
3 5 3
4 5 4
3 4 4

Ohoo.out

3

Explicație

Alegem drumul 1-2-3-5 folosind o putere maximă de 3.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("Ohoo.in");
ofstream cout("Ohoo.out");

int n, m, rez;
vector<vector<pair<int, int>>> G(100001);
queue<int> Q;

bool potajung(int k){
    int P[100001] = {0};
    P[1] = 1;
    Q.push(1);
    while(!Q.empty()){
        int x = Q.front();
        for(auto i:G[x])
            if(!P[i.first] && i.second <= k)
                P[i.first] = 1, Q.push(i.first);
        Q.pop();
    }
    return P[n] == 1;
}

void CB(){
    int st = 0, dr = 1000000;
    int mij = 0;
    while(st <= dr){
        mij = (st + dr) / 2;
        if(potajung(mij)){
            rez = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    if(potajung(dr))
        rez = dr;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        cin >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }
    CB();
    cout << rez;
    return 0;
}