- Pradinių duomenų failas:
- autobusas.in
- Rezultatų failas:
- autobusas.out
- Laiko apribojimas:
- 2 s.
- Atminties apribojimas:
- 16 Mb.
Užduotis
Kaip manote, ar Amerikoj tikrai vaikus į mokyklą vežioja tokie geltoni ir faini autobusai, kokius mes matom filmuose?.. Na, jei vežioja, tai turbūt juos vairuoja apkūnūs dėdės, mėgstantys ilgai pamiegoti. Matyt, jie kiekvieną rytą galvoja:
Ak, kodėl aš turiu keltis taip anksti?.. Tik tam, kad surankiočiau visus tuos vaikus iš velniai žino kur… O jų tiek daug. Kažin, gal galėčiau kaip nors sutaupyti laiko, jei važiuočiau trumpesniu maršrutu? Bent penkiolika minučių saldaus miego…
Tuomet vairuotojai keliasi, pėdina iki mokyklų, sėda į autobusus, apvažiuoja visas sankryžas, kuriose laukia vaikai, ir nuveža juos į mokyklą.
Kiekvienas maršrutas prasideda ir baigiasi sankryžoje prie mokyklos. O be to, kad moksleiviai neįprastų vėluoti į autobusą, pro kiekvieną sankryžą pravažiuojama lygiai vieną kartą.
Parašykite programą, kuri, žinodama atstumus tarp sankryžų bei dabartinį vairuotojo maršrutą, rastų, kiek daugiausiai miego galima sutaupyti, važiuojant geresniu maršrutu.
Pradiniai duomenys
Pirmoje pradinių duomenų failo eilutėje įrašyti du sveikieji skaičiai N ir M (1 <= N <= 15). N yra sankryžų, kuriose vaikai laukia autobuso, skaičius. Sankryžos sunumeruotos nuo 1 iki N; sankryžoje nr. 1 yra prie mokyklos (joje vairuotojas pradeda savo rytinę kelionę). M – yra rajono gatvių skaičius.
Sekančiose M eilučių surašyti sveikų skaičių trejetai \(a_{i}\), \(b_{i}\) ir \(d_{i}\): (\(a_{i}\), \(b_{i}\)) žymi sankryžų porą, kurią jungia \(d_{i}\) metrų ilgio gatvė (\(d_{i}\) <= 5000). Kiekvieną sankryžų porą jungia ne daugiau negu viena gatvė.
Paskutinėje eilutėje įrašyta N + 1 skaičių seka – tai dabartinis vairuotojo maršrutas: skaičiai nurodo, kuria tvarka apvažiuojamos sankryžos. Ši seka yra korektiška: lygiai vieną kartą aplankomos visos sankryžos, pradedama ir baigiama pirmojoje sankryžoje.
Rezultatai
Jei dabartinis vairuotojo maršrutas yra optimalus, į pirmą rezultatų failo eilutę programa turi įrašyti sakinį Ilgiau pamiegoti nepavyks..
Priešingu atveju, į pirmą eilutę programa turi įrašyti sakinį Galima pamiegoti dar m min., kur m – minučių skaičius, kurį vairuotojas sutaupytų, jei važiuotų optimaliu maršrutu (vienam kilometrui nuvažiuoti vidutiniškai sugaištamos 5 minutės, programa atsakymą turi suapvalinti iki minučių tikslumo).
Pavyzdžiai
| Pradiniai duomenys | Rezultatai |
|---|---|
6 10 1 3 1000 1 4 2500 1 6 1500 2 3 1500 2 4 1000 2 5 5000 3 5 2000 3 6 1000 4 5 500 5 6 1500 1 6 5 3 2 4 1 |
Galima pamiegoti dar 15 min. |
6 10 1 3 1000 1 4 2500 1 6 1500 2 3 1500 2 4 1000 2 5 5000 3 5 2000 3 6 1000 4 5 500 5 6 1500 1 6 5 4 2 3 1 |
Ilgiau pamiegoti nepavyks. |