3325 - Ohoo

Cerinta

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 iesire

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.

Restrictii si precizari:

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

5 6

1 2 3

1 4 1

2 3 2

3 5 3

4 5 4

3 4 4

Ohoo.out

3

Explicatie

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

Rezolvare

<syntaxhighlight lang="python3"> from collections import defaultdict

def dfs(node, d):

   global t
   if node == n:
       t = True
   else:
       vis[node] = True
       for i, c in graph[node]:
           if not t and c <= d and not vis[i]:
               dfs(i, d)

def main():

   global n, m, vis, t, graph
   with open("Ohoo.in", "r") as fin:
       n, m = map(int, fin.readline().split())
       graph = defaultdict(list)
       mz = 0

       for _ in range(m):
           x, y, c = map(int, fin.readline().split())
           graph[x].append((y, c))
           graph[y].append((x, c))
           mz = max(mz, c)

   st, dr, sol = 1, mz, mz
   while st <= dr:
       mij = (st + dr) // 2
       vis = [False] * (n + 1)
       t = False
       dfs(1, mij)
       if t:
           sol = mij
           dr = mij - 1
       else:
           st = mij + 1

   with open("Ohoo.out", "w") as fout:
       fout.write(str(sol) + '\n')

if __name__ == "__main__":

   main()

</syntaxhighlight>