206
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; }
Comentarii