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.
Pentru că porumbeii obosesc din cauza zborului ei trebuie sa se odihneasca pe statui, astfel armata poate merge doar pe drumurile cunoscute dintre două statui. Există n statui, iar armata se află inițial pe statuia cu numărul 1, iar cetatea ciorilor se va afla pe cea cu numărul n.
Armata porumbeilor deține un cioc bionic de putere K. Acesta poate sparge garduri cu rezistență mai mica sau egala cu K, armata putând astfel să treacă pe acel drum.
Generalul armatei porumbeilor vă cere să găsiți puterea minimă pe care o poate avea ciocul bionic pentru ca armata să poată ajunge la cetatea ciorilor.

Date de intrare

Fișierul de intrare Ohoo.in va conține: Pe prima linie numărul natural n reprezentând numărul de statui și numărul natural m reprezentând numărul de drumuri existente între statui. Pe următoarele m linii se vor găsi câte 3 numere: x, y, r, cu semnificația că există un drum bidirecțional între statuile x și y blocat de un gard de rezistență r.

Date de ieșire

Fișierul de ieșire Ohoo.out va conține un singur număr natural K, reprezentând puterea minimă pe care o poate avea ciocul bionic astfel încât armata să poată ajunge la cetatea ciorilor.

Restricții și precizări:

2 ≤ n ≤ 100.000
1 ≤ m ≤ 250.000
Rezistențele gardurilor sunt numere naturale nenule și nu depășesc 1.000.000
Între două statui pot exista mai multe drumuri cu garduri de rezistențe diferite
Întotdeauna există soluție
Pentru 60% din teste n ≤ 1000 și K ≤ 1000
Se acordă 10 puncte pentru exemplu
Atenție la numele fișirelor de intrare și de ieșire!

Exemplu

Ohoo.in

Ohoo.out

Explicație

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Ohoo:

#include <bits/stdc++.h>
#define NM 100005
using namespace std;
ifstream fin ("Ohoo.in");
ofstream fout ("Ohoo.out");
void read();
int n, m, maxx, st, dr, rez, mijl;
vector<pair<int,int>> v[NM];
bitset<NM> viz;
bool ok(int nod)
{
    if(viz[n])
        return 1;
    bool gasit = 0;
    viz[nod] = 1;
    if(nod == n)
        return 1;
    for(auto it:v[nod])
        if(!viz[it.first] && it.second <= mijl)
            gasit|=ok(it.first);
    return gasit;
}
int main()
{
    read();
    st = 1, dr = maxx, rez = maxx;
    while(st<=dr)
    {
        mijl = (st+dr)/2;
        viz.reset();
        if(ok(1))
        {
            rez = mijl;
            dr = mijl-1;
        }
        else st = mijl+1;
    }
    fout << rez;
    return 0;
}
void read()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int x, y, p;
        fin >> x >> y >> p;
        maxx = max(maxx, p);
        v[x].push_back({y, p});
        v[y].push_back({x, p});
    }
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3325 Ohoo

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3325 Ohoo de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3325 Ohoo