Fişierul intrare/ieşire:meta.in, meta.outSursăad-hoc
AutorAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Meta (clasele 11-12)

Elevii de la cercul de informatică înţeleg atât de bine algoritmii pentru găsirea arborelui parţial de cost minim, încât îi pot implementa şi cu ochii închişi. De aceea, profesorul le-a dat o problemă ceva mai grea: găsirea celui de-al doilea arbore parţial în ordinea costului.

Se dă un graf neorientat conex cu N noduri şi M muchii. Fiecare muchie are un cost pozitiv asociat şi toate muchiile au costuri diferite. Ajutaţi-i pe elevii de la cerc să calculeze costul celui de-al doilea arbore parţial minim. Mai exact, se cere cel mai mic număr natural K cu proprietăţile:

  1. Există un arbore parţial de cost total K.
  2. K este strict mai mare decât costul arborelui parţial de cost minim pentru graful dat.

Date de intrare

Fişierul de intrare meta.in conţine pe prima linie numerele N şi M, despărţite printr-un spaţiu. Pe următoarele M linii se găseşte câte o pereche de numere x y c cu semnificaţia că între nodurile x şi y există o muchie de cost c.

Date de ieşire

În fişierul de ieşire meta.out se va tipări doar numărul K.

Restricţii

  • 1 ≤ N ≤ 1.000
  • 1 ≤ M ≤ 300.000
  • M ≥ N
  • Nodurile sunt numerotate de la 1 la N.
  • Costurile muchiilor sunt numere naturale distincte cuprinse între 1 şi 1.000.000.

Exemplu

meta.inmeta.out
5 6
1 2 1
2 4 5
4 3 2
3 1 7
3 5 4
4 5 9
14

Explicaţie

Arborele parţial de cost minim are cost 12 şi este format din muchiile (1, 2), (2, 4), (4, 3), (3, 5). Al doilea arbore în ordinea costului are costul 14 şi este format din muchiile (1, 2), (1, 3), (3, 4), (3, 5).

Trebuie sa te autentifici pentru a trimite solutii. Click aici