Tehtävänanto
JOI-kuningaskunta on $N$ kaupungista koostuva kuningaskunta, ja nämä kaupungit on numeroitu $1$:stä $N$:ään. JOI-kuningaskunnassa on $M$ näitä kaupunkeja yhdistävää yksisuuntaista moottoritietä, jotka on numeroitu $1$:stä $M$:ään. Kulkemalla moottoritietä $i$ ($1 \le i \le M$) pääsee kaupungista $A_i$ kaupunkiin $B_i$, ja sen kulkemiseen kuluva aika on $L_i$.
Joka kerta, kun moottoritietä kuljetaan, peritään tietulli. Moottoritien $i$ tietulli on halvimmillaan $C_i$, mutta koska kaikki JOI-kuningaskunnan työntekijät inhoavat ylityötä, tietulli kasvaa sitä suuremmaksi, mitä kauempana aika on vertailuajankohdasta $0$. Tarkemmin sanottuna, jos kaupungista $A_i$ lähdetään ajanhetkellä $t$ ja kuljetaan moottoritietä $i$, tietulli ilmaistaan vakion $K$ avulla muodossa $C_i + K \times |t|$, missä $|t|$ tarkoittaa luvun $t$ itseisarvoa.
Asut kaupungissa $1$ ja suunnittelet matkaa kaupunkiin $N$, jossa ystäväsi asuu. Koska haluat matkustaa kaupungista $1$ kaupunkiin $N$ moottoriteitä pitkin, haluat ensin selvittää, onko se mahdollista, ja jos se on mahdollista, haluat myös selvittää, mikä on pienin mahdollinen tietullien kokonaissumma. Voit valita vapaasti matkareitin sekä lähtöajankohdat kustakin kaupungista. Erityisesti voit lähteä kaupungista $1$ negatiivisella ajanhetkellä tai viettää aikaa pysyttelemällä jossakin kaupungissa kulkematta mitään moottoritietä.
Kun moottoriteiden tiedot sekä vakio $K$ on annettu, kirjoita ohjelma, joka selvittää, onko mahdollista matkustaa kaupungista $1$ kaupunkiin $N$ moottoriteitä pitkin, ja jos se on mahdollista, etsii tietullien kokonaissumman pienimmän arvon.
Tämän tehtävän rajoitusten puitteissa voidaan todistaa, että jos kaupungista $1$ on mahdollista matkustaa kaupunkiin $N$ moottoriteitä pitkin, tietullien kokonaissumman pienin arvo on aina kokonaisluku.
Rajoitukset
- $2 \le N \le 4\,000$.
- $1 \le M \le 8\,000$.
- $0 \le K \le 100\,000$.
- $1 \le A_i \le N$ ($1 \le i \le M$).
- $1 \le B_i \le N$ ($1 \le i \le M$).
- $A_i \neq B_i$ ($1 \le i \le M$).
- $1 \le L_i \le 1\,000\,000$ ($1 \le i \le M$).
- $0 \le C_i \le 10^9$ ($1 \le i \le M$).
- Kaikki syötteen arvot ovat kokonaislukuja.
Osatehtävät
- ($9$ pistettä) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$ pistettä) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$ pistettä) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$ pistettä) $N \le 100$, $M \le 200$, ja seuraava rajoitus pätee:
- $N$ on parillinen, ja $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$), missä $\lfloor x \rfloor$ tarkoittaa suurinta kokonaislukua, joka on enintään $x$.
- ($16$ pistettä) $N \le 100$, $M \le 200$.
- ($11$ pistettä) $N \le 1\,500$, $M \le 3\,000$.
- ($7$ pistettä) Ei lisärajoituksia.
Syöte
Syöte annetaan seuraavassa muodossa:
N M K A_1 B_1 L_1 C_1 A_2 B_2 L_2 C_2 : A_M B_M L_M C_M
Tuloste
Jos kaupungista $1$ on mahdotonta matkustaa kaupunkiin $N$ moottoriteitä pitkin, tulosta -1. Jos se on mahdollista, tulosta $1$ riville kokonaisluku, joka ilmaisee tietullien kokonaissumman pienimmän arvon.
Esimerkki 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
JOI-kuningaskunnan kaupungit ja tiet on esitetty alla olevassa kuvassa. Ympyrät esittävät kaupunkeja, nuolet esittävät teitä, ja kunkin tien viereen on kirjoitettu kyseisen tien arvot $L_i$ ja $C_i$ tässä järjestyksessä. Ympyrän sisään kirjoitettu luku ilmaisee kyseisen kaupungin numeron.
Kun matkustetaan seuraavasti, tietullien kokonaissummaksi tulee $15$:
- Ajanhetki $-1$: Lähde kaupungista $1$ ja suuntaa kaupunkiin $3$. Tietullia kuluu $10 + 2 \times |-1| = 12$.
- Ajanhetki $0$: Saavu kaupunkiin $3$ ja suuntaa välittömästi kaupunkiin $4$. Tietullia kuluu $3 + 2 \times |0| = 3$.
- Ajanhetki $5$: Saavu kaupunkiin $4$.
Koska ei ole tapaa matkustaa siten, että tietullien kokonaissumma olisi pienempi kuin $15$, tulostetaan $15$.
Tämä esimerkkisyöte täyttää osatehtävien $2, 5, 6, 7$ rajoitukset.
Esimerkki 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
Eroaa Esimerkistä $1$ vain vakion $K$ arvon osalta.
Kun matkustetaan seuraavasti, tietullien kokonaissummaksi tulee $9$:
- Ajanhetki $-3$: Lähde kaupungista $1$ ja suuntaa kaupunkiin $2$. Tietullia kuluu $2 + 0 \times |-3| = 2$.
- Ajanhetki $0$: Saavu kaupunkiin $2$ ja suuntaa välittömästi kaupunkiin $3$. Tietullia kuluu $4 + 0 \times |0| = 4$.
- Ajanhetki $1$: Saavu kaupunkiin $3$ ja jää kaupunkiin $3$.
- Ajanhetki $3$: Lähde kaupungista $3$ ja suuntaa kaupunkiin $4$. Tietullia kuluu $3 + 0 \times |3| = 3$.
- Ajanhetki $8$: Saavu kaupunkiin $4$.
Koska ei ole tapaa matkustaa siten, että tietullien kokonaissumma olisi pienempi kuin $9$, tulostetaan $9$.
Tämä esimerkkisyöte täyttää osatehtävien $1, 2, 5, 6, 7$ rajoitukset.
Esimerkki 3
2 1 10 2 1 4 7
-1
Koska kaupungista $1$ on mahdotonta matkustaa kaupunkiin $2$ moottoriteitä pitkin, tulostetaan -1.
Tämä esimerkkisyöte täyttää osatehtävien $2, 5, 6, 7$ rajoitukset.
Esimerkki 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
Tämä esimerkkisyöte täyttää osatehtävien $2, 3, 5, 6, 7$ rajoitukset.
Esimerkki 5
8 8 2 1 2 1 5 5 6 3 1 2 4 10 18 3 5 3 1 1 3 4 2 5 6 2 2 2 5 2 3 6 8 1 1
25
Voi olla olemassa useita teitä, joilla on sama pari $(A_i, B_i)$.
Tämä esimerkkisyöte täyttää osatehtävien $2, 4, 5, 6, 7$ rajoitukset.
Esimerkki 6
6 10 100000 4 2 212037 752027141 2 5 667097 1571491 2 1 769275 576006950 1 2 711969 526189398 5 3 733555 206320177 3 4 364807 802102091 1 4 467240 183184247 3 5 44994 15991843 5 3 613192 782356546 4 6 832593 639529758
47546714005
Tämä esimerkkisyöte täyttää osatehtävien $5, 6, 7$ rajoitukset.