Treść zadania
Królestwo JOI to królestwo składające się z $N$ miast, ponumerowanych od $1$ do $N$. W Królestwie JOI znajduje się $M$ jednokierunkowych autostrad łączących te miasta, ponumerowanych od $1$ do $M$. Jadąc autostradą $i$ ($1 \le i \le M$), można przemieścić się z miasta $A_i$ do miasta $B_i$, a czas potrzebny na jej pokonanie wynosi $L_i$.
Za każdym razem, gdy przejeżdża się autostradą, naliczana jest opłata drogowa. Opłata za autostradę $i$ w najtańszym momencie wynosi $C_i$, ale ponieważ wszyscy pracownicy w Królestwie JOI nie cierpią pracy w godzinach nadliczbowych, im dalej od pewnego czasu odniesienia $0$, tym wyższa staje się opłata. Dokładniej, jeśli wyruszy się z miasta $A_i$ w chwili $t$ i przejedzie autostradą $i$, opłata drogowa wyraża się za pomocą stałej $K$ jako $C_i + K \times |t|$, gdzie $|t|$ oznacza wartość bezwzględną liczby $t$.
Mieszkając w mieście $1$, planujesz podróż do miasta $N$, w którym mieszka twój przyjaciel. Ponieważ chcesz dostać się z miasta $1$ do miasta $N$ korzystając z autostrad, najpierw chcesz sprawdzić, czy jest to możliwe, a jeśli tak, chcesz również wyznaczyć minimalną możliwą sumę opłat drogowych. Możesz przy tym dowolnie wybrać trasę podróży oraz momenty wyjazdu z poszczególnych miast. W szczególności możesz wyruszyć z miasta $1$ w ujemnej chwili czasu lub spędzić pewien czas pozostając w jakimś mieście bez przejeżdżania żadną autostradą.
Mając dane informacje o autostradach oraz stałą $K$, napisz program, który rozstrzygnie, czy można przemieścić się z miasta $1$ do miasta $N$ korzystając z autostrad, a jeśli jest to możliwe, wyznaczy minimalną wartość sumy opłat drogowych.
Przy ograniczeniach tego zadania można udowodnić, że jeśli da się przemieścić z miasta $1$ do miasta $N$ korzystając z autostrad, to minimalna wartość sumy opłat drogowych jest zawsze liczbą całkowitą.
Ograniczenia
- $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$).
- Wszystkie wartości wejściowe są liczbami całkowitymi.
Podzadania
- ($9$ punktów) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$ punktów) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$ punktów) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$ punkty) $N \le 100$, $M \le 200$ oraz spełniony jest następujący warunek:
- $N$ jest parzyste oraz $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$), gdzie $\lfloor x \rfloor$ oznacza największą liczbę całkowitą nie większą niż $x$.
- ($16$ punktów) $N \le 100$, $M \le 200$.
- ($11$ punktów) $N \le 1\,500$, $M \le 3\,000$.
- ($7$ punktów) Brak dodatkowych ograniczeń.
Wejście
Wejście podane jest w następującym formacie:
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
Wyjście
Jeśli przemieszczenie się z miasta $1$ do miasta $N$ za pomocą autostrad jest niemożliwe, wypisz -1. Jeśli jest to możliwe, wypisz w $1$ wierszu liczbę całkowitą oznaczającą minimalną wartość sumy opłat drogowych.
Przykład 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
Miasta i drogi Królestwa JOI przedstawiono na poniższym rysunku. Koła oznaczają miasta, strzałki oznaczają drogi, a obok każdej drogi zapisano kolejno wartości $L_i$ oraz $C_i$ dla tej drogi. Liczba wpisana wewnątrz każdego koła oznacza numer danego miasta.
Podróżując w następujący sposób, łączna opłata drogowa wyniesie $15$:
- Chwila $-1$: Wyrusz z miasta $1$ i udaj się do miasta $3$. Koszt opłaty drogowej wynosi $10 + 2 \times |-1| = 12$.
- Chwila $0$: Dotrzyj do miasta $3$ i natychmiast udaj się do miasta $4$. Koszt opłaty drogowej wynosi $3 + 2 \times |0| = 3$.
- Chwila $5$: Dotrzyj do miasta $4$.
Ponieważ nie istnieje sposób podróży o łącznej opłacie drogowej mniejszej niż $15$, należy wypisać $15$.
Ten przykład wejściowy spełnia ograniczenia podzadań $2, 5, 6, 7$.
Przykład 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
Różni się od Przykładu $1$ jedynie wartością $K$.
Podróżując w następujący sposób, łączna opłata drogowa wyniesie $9$:
- Chwila $-3$: Wyrusz z miasta $1$ i udaj się do miasta $2$. Koszt opłaty drogowej wynosi $2 + 0 \times |-3| = 2$.
- Chwila $0$: Dotrzyj do miasta $2$ i natychmiast udaj się do miasta $3$. Koszt opłaty drogowej wynosi $4 + 0 \times |0| = 4$.
- Chwila $1$: Dotrzyj do miasta $3$ i pozostań w mieście $3$.
- Chwila $3$: Wyrusz z miasta $3$ i udaj się do miasta $4$. Koszt opłaty drogowej wynosi $3 + 0 \times |3| = 3$.
- Chwila $8$: Dotrzyj do miasta $4$.
Ponieważ nie istnieje sposób podróży o łącznej opłacie drogowej mniejszej niż $9$, należy wypisać $9$.
Ten przykład wejściowy spełnia ograniczenia podzadań $1, 2, 5, 6, 7$.
Przykład 3
2 1 10 2 1 4 7
-1
Ponieważ nie da się przemieścić z miasta $1$ do miasta $2$ korzystając z autostrad, należy wypisać -1.
Ten przykład wejściowy spełnia ograniczenia podzadań $2, 5, 6, 7$.
Przykład 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
Ten przykład wejściowy spełnia ograniczenia podzadań $2, 3, 5, 6, 7$.
Przykład 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
Może istnieć wiele dróg mających tę samą parę $(A_i, B_i)$.
Ten przykład wejściowy spełnia ograniczenia podzadań $2, 4, 5, 6, 7$.
Przykład 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
Ten przykład wejściowy spełnia ograniczenia podzadań $5, 6, 7$.