Testo del problema
Il Regno di JOI è un regno composto da $N$ città, numerate da $1$ a $N$. Nel Regno di JOI ci sono $M$ autostrade a senso unico che collegano queste città, numerate da $1$ a $M$. Percorrendo l'autostrada $i$ ($1 \le i \le M$), è possibile spostarsi dalla città $A_i$ alla città $B_i$, e il tempo necessario per percorrerla è $L_i$.
Ogni volta che si percorre un'autostrada, si paga un pedaggio. Il pedaggio per l'autostrada $i$ è pari a $C_i$ nel momento più economico, ma poiché tutti i lavoratori del Regno di JOI detestano il lavoro straordinario, più ci si allontana da un istante di riferimento $0$, più il pedaggio aumenta. Nello specifico, se si parte dalla città $A_i$ all'istante $t$ e si percorre l'autostrada $i$, il pedaggio è espresso tramite una costante $K$ come $C_i + K \times |t|$, dove $|t|$ indica il valore assoluto di $t$.
Tu, che vivi nella città $1$, stai pianificando un viaggio verso la città $N$, dove vive un tuo amico. Poiché desideri viaggiare dalla città $1$ alla città $N$ utilizzando le autostrade, vuoi innanzitutto verificare se ciò sia possibile e, in caso affermativo, vuoi anche determinare quale sia la somma minima possibile dei pedaggi. Qui puoi scegliere liberamente sia il percorso di viaggio sia il momento di partenza da ciascuna città. In particolare, puoi partire dalla città $1$ a un istante negativo, oppure trascorrere del tempo fermandoti in qualche città senza percorrere alcuna autostrada.
Date le informazioni sulle autostrade e la costante $K$, scrivi un programma per determinare se sia possibile viaggiare dalla città $1$ alla città $N$ utilizzando le autostrade e, se possibile, trovare il valore minimo della somma dei pedaggi.
Sotto i vincoli di questo problema, si può dimostrare che, se è possibile viaggiare dalla città $1$ alla città $N$ utilizzando le autostrade, il valore minimo della somma dei pedaggi è sempre un numero intero.
Vincoli
- $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$).
- Tutti i valori di input sono numeri interi.
Subtask
- ($9$ punti) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$ punti) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$ punti) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$ punti) $N \le 100$, $M \le 200$, e vale il seguente vincolo:
- $N$ è pari, e $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$), dove $\lfloor x \rfloor$ indica il massimo intero minore o uguale a $x$.
- ($16$ punti) $N \le 100$, $M \le 200$.
- ($11$ punti) $N \le 1\,500$, $M \le 3\,000$.
- ($7$ punti) Nessun vincolo aggiuntivo.
Input
L'input è fornito nel seguente formato:
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
Output
Se è impossibile viaggiare dalla città $1$ alla città $N$ utilizzando le autostrade, stampa -1. Se è possibile, stampa su $1$ riga l'intero che rappresenta il valore minimo della somma dei pedaggi.
Esempio 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
Le città e le strade del Regno di JOI sono illustrate nella figura seguente. I cerchi rappresentano le città, le frecce rappresentano le strade e accanto a ciascuna strada sono scritti, in quest'ordine, i valori di $L_i$ e $C_i$ di quella strada. Il numero scritto all'interno di ciascun cerchio rappresenta il numero di quella città.
Viaggiando nel modo seguente, la somma dei pedaggi diventa $15$:
- Istante $-1$: Parti dalla città $1$ e dirigiti verso la città $3$. Il pedaggio costa $10 + 2 \times |-1| = 12$.
- Istante $0$: Arriva alla città $3$ e dirigiti immediatamente verso la città $4$. Il pedaggio costa $3 + 2 \times |0| = 3$.
- Istante $5$: Arriva alla città $4$.
Poiché non esiste alcun modo di viaggiare con una somma dei pedaggi inferiore a $15$, stampa $15$.
Questo esempio di input soddisfa i vincoli dei Subtask $2, 5, 6, 7$.
Esempio 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
Differisce dall'Esempio $1$ solo per il valore di $K$.
Viaggiando nel modo seguente, la somma dei pedaggi diventa $9$:
- Istante $-3$: Parti dalla città $1$ e dirigiti verso la città $2$. Il pedaggio costa $2 + 0 \times |-3| = 2$.
- Istante $0$: Arriva alla città $2$ e dirigiti immediatamente verso la città $3$. Il pedaggio costa $4 + 0 \times |0| = 4$.
- Istante $1$: Arriva alla città $3$ e rimani nella città $3$.
- Istante $3$: Parti dalla città $3$ e dirigiti verso la città $4$. Il pedaggio costa $3 + 0 \times |3| = 3$.
- Istante $8$: Arriva alla città $4$.
Poiché non esiste alcun modo di viaggiare con una somma dei pedaggi inferiore a $9$, stampa $9$.
Questo esempio di input soddisfa i vincoli dei Subtask $1, 2, 5, 6, 7$.
Esempio 3
2 1 10 2 1 4 7
-1
Poiché è impossibile viaggiare dalla città $1$ alla città $2$ utilizzando le autostrade, stampa -1.
Questo esempio di input soddisfa i vincoli dei Subtask $2, 5, 6, 7$.
Esempio 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
Questo esempio di input soddisfa i vincoli dei Subtask $2, 3, 5, 6, 7$.
Esempio 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
Possono esistere più strade aventi la stessa coppia $(A_i, B_i)$.
Questo esempio di input soddisfa i vincoli dei Subtask $2, 4, 5, 6, 7$.
Esempio 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
Questo esempio di input soddisfa i vincoli dei Subtask $5, 6, 7$.