- Time limit: 2.00 s
- Memory limit: 128 MB
Uolevin kummitäti asuu Vladivostokissa, ja hiihtoloman aikaan Uolevi päätti lähteä käymään tädin luona. Uolevi itse asuu Helsingissä.
Tiedossasi on lentoasemat ja niiden väliset lennot sekä kunkin lennon hinta. Lisäksi Uolevilla on yksi alennuskuponki, jonka avulla hän voi matkustaa puoleen hintaan minkä tahansa reitin varrella olevan lennon.
Mikä on halvin hinta matkalle Helsingistä Vladivostokiin?
Syöte
Syötteen alussa on kaksi kokonaislukua ja : kaupunkien määrä ja yhteyksien määrä. Kaupungit on numeroitu kokonaisluvuin . Kaupunki 1 on Helsinki ja kaupunki on Vladivostok.
Tämän jälkeen syötteessä on riviä, joista jokainen kuvaa yhden lennon. Rivillä on kolme kokonaislukua , ja : mistä kaupungista lento alkaa, mihin kaupunkiin lento päättyy ja mikä on sen hinta. Kaikki lennot ovat yksisuuntaisia.
Jos lennon hinta on , niin sen alennettu hinta on eli pyöristettynä alaspäin kokonaisluvuksi.
Tuloste
Ohjelmasi tulee tulostaa yksi kokonaisluku: halvin hinta matkalle.
Voit olettaa, että jokin reitti on varmasti olemassa.
Rajat
Esimerkki
Syöte:
4 5 1 2 6 2 3 6 3 4 2 1 3 14 4 3 3
Tuloste:
9
Selitys: Uolevi lentää ensin 1->3 käyttäen alennuskupongin (hinta 7). Tämän jälkeen hän lentää 3->4 (hinta 2). Yhteishinta on siis 9.