- Time limit: 1.00 s
- Memory limit: 128 MB
Tehtäväsi on etsiä halvin lentoreitti Syrjälästä Metsälään. Erikoisuutena sinulla on käytössä alennuskuponki, jolla saat puolitettua minkä tahansa reitillä olevan lennon hinnan. Voit kuitenkin puolittaa vain yhden lennon hinnan.
Syöte
Syötteen alussa on kaksi kokonaislukua ja : kaupunkien määrä ja lentoyhteyksien määrä. Kaupungit on numeroitu . Kaupunki 1 on Syrjälä, ja kaupunki on Metsälä.
Sitten syötteessä on riviä, joista jokainen kuvaa yhden lentoyhteyden. Rivillä on kolme kokonaislukua , ja : lento alkaa kaupungista , päättyy kaupunkiin ja sen hinta on . Jokainen lento on yksisuuntainen.
Voit olettaa, että Syrjälästä Metsälään on ainakin yksi reitti.
Tuloste
Tulosta yksi kokonaisluku: halvin reitti Syrjälästä Metsälään.
Kun käytät alennuskupongin lentoon, jonka hinta on , sen hinnaksi tulee (pyöristys alaspäin kokonaisluvuksi).
Rajat
Esimerkki
Syöte:
3 4 1 2 3 2 3 1 1 3 7 2 1 5
Tuloste:
2