Problembeskrivning
Kungariket JOI är ett kungarike som består av $N$ städer, numrerade från $1$ till $N$. I Kungariket JOI finns det $M$ enkelriktade motorvägar som förbinder dessa städer, numrerade från $1$ till $M$. Genom att ta motorväg $i$ ($1 \le i \le M$) kan man resa från stad $A_i$ till stad $B_i$, och tiden det tar att färdas längs den är $L_i$.
Varje gång man färdas längs en motorväg tillkommer en vägtull. Vägtullen för motorväg $i$ är som billigast $C_i$, men eftersom alla arbetare i Kungariket JOI ogillar övertidsarbete blir vägtullen högre ju längre bort tiden ligger från en referenstidpunkt $0$. Mer specifikt, om man avreser från stad $A_i$ vid tidpunkten $t$ och färdas längs motorväg $i$, uttrycks vägtullen med hjälp av en konstant $K$ som $C_i + K \times |t|$, där $|t|$ betecknar absolutbeloppet av $t$.
Du som bor i stad $1$ planerar en resa till stad $N$, där din vän bor. Eftersom du vill resa från stad $1$ till stad $N$ via motorvägar vill du först kontrollera om det är möjligt, och om det är möjligt vill du också ta reda på vad den minsta möjliga totala vägtullen är. Här får du fritt välja resväg och tidpunkt för avresa från varje stad. I synnerhet får du avresa från stad $1$ vid en negativ tidpunkt, eller tillbringa tid med att stanna i någon stad utan att färdas längs någon motorväg.
Givet informationen om motorvägarna och konstanten $K$, skriv ett program som avgör om det är möjligt att resa från stad $1$ till stad $N$ via motorvägar och, om det är möjligt, beräknar den minsta totala vägtullen.
Under begränsningarna i detta problem kan det bevisas att om det är möjligt att resa från stad $1$ till stad $N$ via motorvägar så är den minsta totala vägtullen alltid ett heltal.
Begränsningar
- $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$).
- Alla indatavärden är heltal.
Delproblem
- ($9$ poäng) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$ poäng) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$ poäng) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$ poäng) $N \le 100$, $M \le 200$, och följande begränsning gäller:
- $N$ är jämnt, och $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$), där $\lfloor x \rfloor$ betecknar det största heltalet som är mindre än eller lika med $x$.
- ($16$ poäng) $N \le 100$, $M \le 200$.
- ($11$ poäng) $N \le 1\,500$, $M \le 3\,000$.
- ($7$ poäng) Inga ytterligare begränsningar.
Indata
Indata ges i följande format:
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
Utdata
Om det är omöjligt att resa från stad $1$ till stad $N$ via motorvägar, skriv ut -1. Om det är möjligt, skriv ut på $1$ rad det heltal som representerar den minsta totala vägtullen.
Exempel 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
Städerna och vägarna i Kungariket JOI illustreras nedan. Cirklar representerar städer, pilar representerar vägar, och bredvid varje väg står värdena på $L_i$ och $C_i$ för den vägen i denna ordning. Talet som står inuti varje cirkel representerar numret på den staden.
Genom att resa på följande sätt blir den totala vägtullen $15$:
- Tidpunkt $-1$: Avres från stad $1$ och åk mot stad $3$. Det kostar en vägtull på $10 + 2 \times |-1| = 12$.
- Tidpunkt $0$: Anländ till stad $3$ och åk omedelbart mot stad $4$. Det kostar en vägtull på $3 + 2 \times |0| = 3$.
- Tidpunkt $5$: Anländ till stad $4$.
Eftersom det inte finns något sätt att resa med en total vägtull mindre än $15$, skriv ut $15$.
Detta exempelindata uppfyller begränsningarna för delproblem $2, 5, 6, 7$.
Exempel 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
Endast värdet på $K$ skiljer sig från Exempel $1$.
Genom att resa på följande sätt blir den totala vägtullen $9$:
- Tidpunkt $-3$: Avres från stad $1$ och åk mot stad $2$. Det kostar en vägtull på $2 + 0 \times |-3| = 2$.
- Tidpunkt $0$: Anländ till stad $2$ och åk omedelbart mot stad $3$. Det kostar en vägtull på $4 + 0 \times |0| = 4$.
- Tidpunkt $1$: Anländ till stad $3$ och stanna kvar i stad $3$.
- Tidpunkt $3$: Avres från stad $3$ och åk mot stad $4$. Det kostar en vägtull på $3 + 0 \times |3| = 3$.
- Tidpunkt $8$: Anländ till stad $4$.
Eftersom det inte finns något sätt att resa med en total vägtull mindre än $9$, skriv ut $9$.
Detta exempelindata uppfyller begränsningarna för delproblem $1, 2, 5, 6, 7$.
Exempel 3
2 1 10 2 1 4 7
-1
Eftersom det är omöjligt att resa från stad $1$ till stad $2$ via motorvägar, skriv ut -1.
Detta exempelindata uppfyller begränsningarna för delproblem $2, 5, 6, 7$.
Exempel 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
Detta exempelindata uppfyller begränsningarna för delproblem $2, 3, 5, 6, 7$.
Exempel 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
Det kan finnas flera vägar som har samma par $(A_i, B_i)$.
Detta exempelindata uppfyller begränsningarna för delproblem $2, 4, 5, 6, 7$.
Exempel 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
Detta exempelindata uppfyller begränsningarna för delproblem $5, 6, 7$.