Aufgabenstellung
Das Königreich JOI ist ein Königreich, das aus $N$ Städten besteht, die von $1$ bis $N$ nummeriert sind. Im Königreich JOI gibt es $M$ Einbahn-Autobahnen, die diese Städte verbinden und von $1$ bis $M$ nummeriert sind. Wenn man die Autobahn $i$ ($1 \le i \le M$) benutzt, kann man von Stadt $A_i$ nach Stadt $B_i$ fahren, und die dafür benötigte Fahrzeit beträgt $L_i$.
Jedes Mal, wenn eine Autobahn befahren wird, fällt eine Mautgebühr an. Die Maut für die Autobahn $i$ beträgt im günstigsten Fall $C_i$, aber da alle Arbeiter im Königreich JOI Überstunden verabscheuen, steigt die Maut umso mehr an, je weiter der Zeitpunkt von einer Referenzzeit $0$ entfernt ist. Konkret gilt: Wenn man zum Zeitpunkt $t$ in Stadt $A_i$ aufbricht und die Autobahn $i$ befährt, wird die Maut mithilfe einer Konstanten $K$ als $C_i + K \times |t|$ ausgedrückt, wobei $|t|$ den Absolutbetrag von $t$ bezeichnet.
Sie wohnen in Stadt $1$ und planen einen Ausflug in die Stadt $N$, in der Ihr Freund wohnt. Da Sie über Autobahnen von Stadt $1$ nach Stadt $N$ reisen möchten, wollen Sie zunächst prüfen, ob dies überhaupt möglich ist, und falls ja, wie hoch die minimale Gesamtsumme der Mautgebühren ist. Dabei können Sie die Reiseroute sowie den Abfahrtszeitpunkt in jeder Stadt frei wählen. Insbesondere dürfen Sie auch zu einem negativen Zeitpunkt in Stadt $1$ aufbrechen oder einige Zeit in einer Stadt verweilen, ohne eine Autobahn zu befahren.
Gegeben die Informationen über die Autobahnen sowie die Konstante $K$, schreiben Sie ein Programm, das entscheidet, ob man über Autobahnen von Stadt $1$ nach Stadt $N$ reisen kann, und falls dies möglich ist, den minimalen Gesamtwert der Mautgebühren berechnet.
Unter den Einschränkungen dieser Aufgabe lässt sich beweisen, dass die minimale Gesamtsumme der Mautgebühren stets eine ganze Zahl ist, sofern eine Reise von Stadt $1$ nach Stadt $N$ über Autobahnen möglich ist.
Einschränkungen
- $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$).
- Alle Eingabewerte sind ganze Zahlen.
Teilaufgaben
- ($9$ Punkte) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$ Punkte) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$ Punkte) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$ Punkte) $N \le 100$, $M \le 200$, und die folgende Einschränkung ist erfüllt:
- $N$ ist gerade, und $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$). Hierbei bezeichnet $\lfloor x \rfloor$ die größte ganze Zahl, die kleiner oder gleich $x$ ist.
- ($16$ Punkte) $N \le 100$, $M \le 200$.
- ($11$ Punkte) $N \le 1\,500$, $M \le 3\,000$.
- ($7$ Punkte) Keine weiteren Einschränkungen.
Eingabe
Die Eingabe erfolgt im folgenden 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
Ausgabe
Falls es unmöglich ist, über Autobahnen von Stadt $1$ nach Stadt $N$ zu reisen, geben Sie -1 aus. Falls es möglich ist, geben Sie in $1$ Zeile die ganze Zahl aus, die das Minimum der Gesamtsumme der Mautgebühren darstellt.
Beispiel 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
Die Städte und Straßen des Königreichs JOI sind in der folgenden Abbildung dargestellt. Kreise stellen Städte dar, Pfeile stellen Straßen dar, und neben jeder Straße stehen in dieser Reihenfolge die Werte von $L_i$ und $C_i$ dieser Straße. Die Zahl in einem Kreis gibt die Nummer der jeweiligen Stadt an.
Wenn man wie folgt reist, beträgt die Gesamtsumme der Mautgebühren $15$:
- Zeitpunkt $-1$: Abfahrt von Stadt $1$ in Richtung Stadt $3$. Es fällt eine Maut von $10 + 2 \times |-1| = 12$ an.
- Zeitpunkt $0$: Ankunft in Stadt $3$ und sofortige Weiterfahrt nach Stadt $4$. Es fällt eine Maut von $3 + 2 \times |0| = 3$ an.
- Zeitpunkt $5$: Ankunft in Stadt $4$.
Da es keine Reisemöglichkeit gibt, bei der die Gesamtsumme der Mautgebühren kleiner als $15$ ist, wird $15$ ausgegeben.
Diese Beispieleingabe erfüllt die Einschränkungen der Teilaufgaben $2, 5, 6, 7$.
Beispiel 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
Unterscheidet sich von Beispiel $1$ nur durch den Wert von $K$.
Wenn man wie folgt reist, beträgt die Gesamtsumme der Mautgebühren $9$:
- Zeitpunkt $-3$: Abfahrt von Stadt $1$ in Richtung Stadt $2$. Es fällt eine Maut von $2 + 0 \times |-3| = 2$ an.
- Zeitpunkt $0$: Ankunft in Stadt $2$ und sofortige Weiterfahrt nach Stadt $3$. Es fällt eine Maut von $4 + 0 \times |0| = 4$ an.
- Zeitpunkt $1$: Ankunft in Stadt $3$ und Aufenthalt in Stadt $3$.
- Zeitpunkt $3$: Abfahrt von Stadt $3$ in Richtung Stadt $4$. Es fällt eine Maut von $3 + 0 \times |3| = 3$ an.
- Zeitpunkt $8$: Ankunft in Stadt $4$.
Da es keine Reisemöglichkeit gibt, bei der die Gesamtsumme der Mautgebühren kleiner als $9$ ist, wird $9$ ausgegeben.
Diese Beispieleingabe erfüllt die Einschränkungen der Teilaufgaben $1, 2, 5, 6, 7$.
Beispiel 3
2 1 10 2 1 4 7
-1
Da es unmöglich ist, über Autobahnen von Stadt $1$ nach Stadt $2$ zu reisen, wird -1 ausgegeben.
Diese Beispieleingabe erfüllt die Einschränkungen der Teilaufgaben $2, 5, 6, 7$.
Beispiel 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
Diese Beispieleingabe erfüllt die Einschränkungen der Teilaufgaben $2, 3, 5, 6, 7$.
Beispiel 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
Es kann mehrere Straßen geben, die dasselbe Paar $(A_i, B_i)$ besitzen.
Diese Beispieleingabe erfüllt die Einschränkungen der Teilaufgaben $2, 4, 5, 6, 7$.
Beispiel 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
Diese Beispieleingabe erfüllt die Einschränkungen der Teilaufgaben $5, 6, 7$.