Lýsing á verkefni
Konungsríkið JOI er konungsríki sem samanstendur af $N$ borgum, sem eru númeraðar frá $1$ til $N$. Í Konungsríkinu JOI eru $M$ einstefnu hraðbrautir sem tengja þessar borgir, númeraðar frá $1$ til $M$. Með því að fara um hraðbraut $i$ ($1 \le i \le M$) er hægt að ferðast frá borg $A_i$ til borgar $B_i$, og tíminn sem það tekur að fara um hana er $L_i$.
Í hvert sinn sem farið er um hraðbraut þarf að greiða vegatoll. Vegatollurinn fyrir hraðbraut $i$ er $C_i$ þegar hann er ódýrastur, en þar sem öllum verkamönnum í Konungsríkinu JOI er illa við yfirvinnu hækkar vegatollurinn eftir því sem tíminn er lengra frá viðmiðunartímanum $0$. Nánar tiltekið, ef lagt er af stað frá borg $A_i$ á tíma $t$ og farið um hraðbraut $i$, þá er vegatollurinn táknaður með fasta $K$ sem $C_i + K \times |t|$, þar sem $|t|$ táknar tölugildi $t$.
Þú býrð í borg $1$ og ert að skipuleggja ferð til borgar $N$, þar sem vinur þinn býr. Þar sem þú vilt ferðast frá borg $1$ til borgar $N$ eftir hraðbrautum viltu fyrst athuga hvort það sé hægt, og ef það er hægt viltu einnig finna hver minnsti mögulegi heildarvegatollurinn er. Hér máttu velja ferðaleiðina og tímasetningu brottfarar frá hverri borg að vild. Sér í lagi máttu leggja af stað frá borg $1$ á neikvæðum tíma, eða eyða tíma í að dvelja í einhverri borg án þess að fara um hraðbraut.
Gefnar eru upplýsingar um hraðbrautirnar og fastinn $K$. Skrifaðu forrit til að ákvarða hvort hægt sé að ferðast frá borg $1$ til borgar $N$ eftir hraðbrautum, og ef það er hægt, finndu minnsta mögulega heildarvegatollinn.
Með skorðum þessa verkefnis má sanna að ef hægt er að ferðast frá borg $1$ til borgar $N$ eftir hraðbrautum, þá er minnsti mögulegi heildarvegatollurinn alltaf heiltala.
Skorður
- $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$).
- Öll inntaksgildi eru heiltölur.
Undirverkefni
- ($9$ stig) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$ stig) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$ stig) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$ stig) $N \le 100$, $M \le 200$, og eftirfarandi skorða gildir:
- $N$ er slétt tala, og $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$), þar sem $\lfloor x \rfloor$ táknar stærstu heiltölu sem er minni en eða jöfn $x$.
- ($16$ stig) $N \le 100$, $M \le 200$.
- ($11$ stig) $N \le 1\,500$, $M \le 3\,000$.
- ($7$ stig) Engar viðbótarskorður.
Inntak
Inntakið er gefið á eftirfarandi sniði:
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
Úttak
Ef ómögulegt er að ferðast frá borg $1$ til borgar $N$ eftir hraðbrautum skal prenta -1. Ef það er hægt skal prenta í $1$ línu heiltöluna sem táknar minnsta mögulega heildarvegatollinn.
Dæmi 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
Borgir og vegir Konungsríkisins JOI eru sýndir á myndinni hér að neðan. Hringir tákna borgir, örvar tákna vegi og við hlið hvers vegar eru skrifuð gildin á $L_i$ og $C_i$ fyrir þann veg í þessari röð. Talan sem skrifuð er inni í hverjum hring táknar númer þeirrar borgar.
Með því að ferðast á eftirfarandi hátt verður heildarvegatollurinn $15$:
- Tími $-1$: Lagt af stað frá borg $1$ og haldið til borgar $3$. Það kostar vegatoll upp á $10 + 2 \times |-1| = 12$.
- Tími $0$: Komið til borgar $3$ og haldið strax áfram til borgar $4$. Það kostar vegatoll upp á $3 + 2 \times |0| = 3$.
- Tími $5$: Komið til borgar $4$.
Þar sem engin leið er til að ferðast þannig að heildarvegatollurinn verði minni en $15$, skal prenta $15$.
Þetta sýnidæmi uppfyllir skorður undirverkefna $2, 5, 6, 7$.
Dæmi 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
Aðeins gildið á $K$ er ólíkt Dæmi $1$.
Með því að ferðast á eftirfarandi hátt verður heildarvegatollurinn $9$:
- Tími $-3$: Lagt af stað frá borg $1$ og haldið til borgar $2$. Það kostar vegatoll upp á $2 + 0 \times |-3| = 2$.
- Tími $0$: Komið til borgar $2$ og haldið strax áfram til borgar $3$. Það kostar vegatoll upp á $4 + 0 \times |0| = 4$.
- Tími $1$: Komið til borgar $3$ og dvalið áfram í borg $3$.
- Tími $3$: Lagt af stað frá borg $3$ og haldið til borgar $4$. Það kostar vegatoll upp á $3 + 0 \times |3| = 3$.
- Tími $8$: Komið til borgar $4$.
Þar sem engin leið er til að ferðast þannig að heildarvegatollurinn verði minni en $9$, skal prenta $9$.
Þetta sýnidæmi uppfyller skorður undirverkefna $1, 2, 5, 6, 7$.
Dæmi 3
2 1 10 2 1 4 7
-1
Þar sem ómögulegt er að ferðast frá borg $1$ til borgar $2$ eftir hraðbrautum skal prenta -1.
Þetta sýnidæmi uppfyllir skorður undirverkefna $2, 5, 6, 7$.
Dæmi 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
Þetta sýnidæmi uppfyllir skorður undirverkefna $2, 3, 5, 6, 7$.
Dæmi 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
Það geta verið margir vegir sem hafa sama parið $(A_i, B_i)$.
Þetta sýnidæmi uppfyllir skorður undirverkefna $2, 4, 5, 6, 7$.
Dæmi 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
Þetta sýnidæmi uppfyllir skorður undirverkefna $5, 6, 7$.