- Time limit: 1.00 s
- Memory limit: 128 MB
Pelaat peliä, jossa on tasoa ja niiden välillä teleporttia. Jokaiseen teleporttiin liittyy tietty hinta.
Tehtäväsi on päästä tasolta tasolle tasan teleportin kautta. Mikä on halvin kokonaishinta tähän?
Syöte
Syötteen ensimmäisellä rivillä on kolme kokonaislukua , ja : tasojen määrä, teleporttien määrä ja askelten määrä. Tasot on numeroitu kokonaisluvuin .
Sitten syötteessä on riviä, joista jokainen kuvaa yhden teleportin. Rivillä on kolme kokonaislukua , ja : teleportti vie tasolta tasolle ja sen hinta on .
Tuloste
Tulosta halvin mahdollinen reitin hinta. Voit olettaa, että ainakin yksi reitti on olemassa.
Rajat
Esimerkki
Syöte:
3 4 8 1 2 5 2 3 4 3 1 1 3 2 2
Tuloste:
27