Énoncé du problème
Le royaume de JOI est un royaume constitué de $N$ villes, numérotées de $1$ à $N$. Dans le royaume de JOI, il y a $M$ autoroutes à sens unique reliant ces villes, numérotées de $1$ à $M$. En empruntant l'autoroute $i$ ($1 \le i \le M$), on peut aller de la ville $A_i$ à la ville $B_i$, et le temps nécessaire pour la parcourir est $L_i$.
Chaque fois que l'on emprunte une autoroute, un péage doit être payé. Le péage de l'autoroute $i$ est au minimum de $C_i$, mais comme tous les travailleurs du royaume de JOI détestent les heures supplémentaires, plus l'heure est éloignée d'un instant de référence $0$, plus le péage augmente. Plus précisément, si l'on quitte la ville $A_i$ à l'instant $t$ pour emprunter l'autoroute $i$, le péage s'exprime à l'aide d'une constante $K$ par la formule $C_i + K \times |t|$, où $|t|$ désigne la valeur absolue de $t$.
Habitant dans la ville $1$, vous prévoyez de rendre visite à un ami qui habite dans la ville $N$. Comme vous souhaitez aller de la ville $1$ à la ville $N$ par l'autoroute, vous voulez d'abord vérifier si cela est possible, et si oui, déterminer quelle est la somme minimale possible des péages. Vous pouvez choisir librement votre itinéraire ainsi que l'instant de départ de chaque ville. En particulier, vous pouvez partir de la ville $1$ à un instant négatif, ou encore passer du temps à attendre dans une ville sans emprunter d'autoroute.
Étant donné les informations sur les autoroutes et la constante $K$, écrivez un programme permettant de déterminer s'il est possible d'aller de la ville $1$ à la ville $N$ en empruntant les autoroutes, et si c'est possible, de trouver la valeur minimale de la somme des péages.
Sous les contraintes de ce problème, on peut démontrer que s'il est possible d'aller de la ville $1$ à la ville $N$ par les autoroutes, la somme minimale des péages est toujours un entier.
Contraintes
- $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$).
- Toutes les valeurs d'entrée sont des entiers.
Sous-tâches
- ($9$ points) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$ points) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$ points) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$ points) $N \le 100$, $M \le 200$, et la contrainte suivante est satisfaite :
- $N$ est pair, et $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$), où $\lfloor x \rfloor$ désigne le plus grand entier inférieur ou égal à $x$.
- ($16$ points) $N \le 100$, $M \le 200$.
- ($11$ points) $N \le 1\,500$, $M \le 3\,000$.
- ($7$ points) Aucune contrainte supplémentaire.
Entrée
L'entrée est donnée dans le format suivant :
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
Sortie
S'il est impossible d'aller de la ville $1$ à la ville $N$ par les autoroutes, affichez -1. Si c'est possible, affichez sur $1$ ligne l'entier représentant la somme minimale des péages.
Exemple 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
Les villes et les routes du royaume de JOI sont représentées sur la figure ci-dessous. Les cercles représentent les villes, les flèches représentent les routes, et à côté de chaque route sont écrits dans cet ordre les nombres $L_i$ et $C_i$ de cette route. Le nombre inscrit dans chaque cercle représente le numéro de la ville.
En se déplaçant comme suit, la somme des péages vaut $15$ :
- Instant $-1$ : Départ de la ville $1$ vers la ville $3$. Le péage coûte $10 + 2 \times |-1| = 12$.
- Instant $0$ : Arrivée à la ville $3$ et départ immédiat vers la ville $4$. Le péage coûte $3 + 2 \times |0| = 3$.
- Instant $5$ : Arrivée à la ville $4$.
Comme il n'existe aucun moyen de se déplacer avec une somme des péages inférieure à $15$, on affiche $15$.
Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 5, 6, 7$.
Exemple 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
Seule la valeur de $K$ diffère de l'Exemple $1$.
En se déplaçant comme suit, la somme des péages vaut $9$ :
- Instant $-3$ : Départ de la ville $1$ vers la ville $2$. Le péage coûte $2 + 0 \times |-3| = 2$.
- Instant $0$ : Arrivée à la ville $2$ et départ immédiat vers la ville $3$. Le péage coûte $4 + 0 \times |0| = 4$.
- Instant $1$ : Arrivée à la ville $3$ et attente dans la ville $3$.
- Instant $3$ : Départ de la ville $3$ vers la ville $4$. Le péage coûte $3 + 0 \times |3| = 3$.
- Instant $8$ : Arrivée à la ville $4$.
Comme il n'existe aucun moyen de se déplacer avec une somme des péages inférieure à $9$, on affiche $9$.
Cet exemple d'entrée satisfait les contraintes des sous-tâches $1, 2, 5, 6, 7$.
Exemple 3
2 1 10 2 1 4 7
-1
Comme il est impossible d'aller de la ville $1$ à la ville $2$ par les autoroutes, on affiche -1.
Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 5, 6, 7$.
Exemple 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 3, 5, 6, 7$.
Exemple 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
Il peut exister plusieurs routes ayant le même couple $(A_i, B_i)$.
Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 4, 5, 6, 7$.
Exemple 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
Cet exemple d'entrée satisfait les contraintes des sous-tâches $5, 6, 7$.