- Nosaukums
- Tālais ceļojums (talcel)
- Laika limits
- 1.00s
- Atmiņas limits
- 32.0 MB
- Grūtība
-
25%
Definīcija
Gudrinieku valstī ir N dažādas pilsētas, numurētas ar skaitļiem no 1 līdz N. Dažus pilsētu pārus savieno divvirzienu ceļi, kuram katram ir savs laiks, kādā to var nostaigāt.
Skots ir tūrists un vēlas apceļot visas pilsētas. Viņam ir savs saraksts, kurā viņš grib apceļot un apskatīt pilsētas (visu N pilsētu konkrēta secība). Ja Skots apskatīja vienu pilsētu un grib nokļūt nākamajā pilsētā sarakstā, tad viņš izvēlas ātrāko maršrutu, lai tur nokļūtu. Skotam nav jāatgriežas sākumā. Ceļojot starp divām pilsētām savā sarakstā, viņš var apmeklēt arī citas pilsētas.
Kaut gan starp katrām divām secīgām pilsētām Skots grib nokļūt pēc iespējas ātrāk, kopumā viņš grib pavadīt savā ceļojumā pēc iespējas vairāk laika. Izrēķiniet, kāds ir ilgākais iespējamais Skota ceļojums!
Ievaddatu raksturojums
Pirmajā rindā dots divi naturāli skaitļi N un M, pilsētu skaits (2 ≤ N ≤ 15) un ceļu skaits (N−1 ≤ M ≤ N(N−1)/2).
Katrā no nākamajām M rindām ir doti trīs skaitļi a, b, c, pilsētas, ko savieno viens ceļš, un tā laiks (1 ≤ a, b ≤ N, 1 ≤ c ≤ 106).
Garantēts, ka no katras virsotnes var nokļūt uz katru citu. Starp katrām divām virsotnēm ir ne vairāk kā viens ceļš.
Izvaddatu raksturojums
Izvadiet vienu skaitli, ilgumu garākajam iespējamam Skota ceļojumam.
Piezīmes
Apakšuzdevuma apraksts | Punktu skaits |
N ≤ 10 | 20 |
Bez papildus ierobežojumiem | 80 |
Kopā: | 100 |
Paraugdati
Stdin
4 3 1 2 3 2 3 4 3 4 5
Stdout
28
Stdin
5 6 5 4 50 5 1 46 3 5 70 3 1 60 2 3 53 4 1 37
Stdout
430
Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.