Fişierul intrare/ieşire:profit.in, profit.outSursăConcurs Shumen seniori 2017
AutorAutor NecunoscutAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Profit

Sunt N oraşe in Olympiland, numerotate de la 1 la N. Unele sunt direct conectate. Există un singur drum posibil de la un oraş la altul, care poate să nu fie neapărat direct (trecând prin alte oraşe).
Pentru a realiza un mare proiect de infrastructură, a fost creată o lisă a rutelor care pot fi utilizate pentru a transporta echipamentul necesar acestui proiect. Un singur transport o sa fie efectuat pe fiecare rută. Un drum este definit de doua orase u si v intre care sunt transportate echipamentele (direcţia nu este importantă) şi un profit p realizat de către compania care o să facă transportul pe ruta respectivă.

Este organizat un concurs pentru companiile care efectuează transportul. Fiecare companie trebuie să aleagă doua oraşe şi trebuie să finalizeze transportul echipamentelor pe toate rutele care încep şi se termină între cele două oraşe (inclusiv acestea). Scrieţi un program care să aleagă doua oraşe din Olympiland pentru a obţine profit maxim prin utilizarea rutelor care se află între cele două oraşe selectate.

Date de intrare

Fişierul de intrare profit.in conţine un număr întreg N reprezentând numărul de oraşe din Olympiland. Fiecare din următoarele N - 1 linii, conţine două numere întregi pozitive (nu mai mari decât N), separate prin spaţii, reprezentând o pereche de oraşe care sunt direct conectate de către un drum. Următoarea linie conţine numărul întreg M reprezentând lungimea listei cu drumurile de transport. Următoarele M linii conţin trei întregi pozitivi separaţi prin spaţii, reprezentând numerele celor două oraşe, ruta şi profitul realizat.

Date de ieşire

În fişierul de ieşire profit.out conţine trei numere întregi separate prin spaţii reprezentând numerele celor două oraşe cu ajutorul cărora se poate ajunge la profit maxim urmat de valoarea profitului maxim. Dacă există mai multe soluţii, se va afişa oricare soluţie corectă.

Restricţii

  • 2 ≤ N ≤ 105
  • 0 ≤ M ≤ 105
  • 1 ≤ profitul fiecărei rute ≤ 103
  • În 20% dintre teste : N < 100
  • În 40% dintre teste : N < 1 000
  • În 70% dintre teste există o rută optimă, inclusiv drumul direct dat in lista drumurilor directe

Exemplu

profit.inprofit.outExplicaţie
6
1 2
2 3
2 4
5 4
6 4
4
1 4 10
2 5 20
6 3 15
2 1 1.
5 1 31
Trebuie sa te autentifici pentru a trimite solutii. Click aici