Đề bài
Vương quốc JOI là một vương quốc gồm $N$ thành phố, các thành phố này được đánh số từ $1$ đến $N$. Tại Vương quốc JOI, có $M$ đường cao tốc một chiều nối các thành phố này, được đánh số từ $1$ đến $M$. Khi đi qua đường cao tốc $i$ ($1 \le i \le M$), ta có thể di chuyển từ thành phố $A_i$ đến thành phố $B_i$, và thời gian cần thiết để đi hết con đường là $L_i$.
Mỗi lần đi qua một đường cao tốc, người đi sẽ phải trả phí cầu đường. Phí đi đường cao tốc $i$ lúc rẻ nhất là $C_i$, nhưng vì tất cả người lao động ở Vương quốc JOI đều ghét làm thêm giờ, nên thời điểm càng xa mốc thời gian chuẩn $0$ thì phí đi đường càng tăng lên. Cụ thể, nếu xuất phát từ thành phố $A_i$ vào thời điểm $t$ và đi qua đường cao tốc $i$, phí đi đường được biểu diễn theo hằng số $K$ là $C_i + K \times |t|$, trong đó $|t|$ biểu thị giá trị tuyệt đối của $t$.
Đang sống tại thành phố $1$, bạn lên kế hoạch đến thăm thành phố $N$ nơi người bạn của mình sinh sống. Vì muốn di chuyển từ thành phố $1$ đến thành phố $N$ qua các đường cao tốc, trước hết bạn muốn kiểm tra xem điều đó có khả thi hay không, và nếu khả thi thì tổng phí đi đường nhỏ nhất có thể là bao nhiêu. Ở đây, bạn có thể tự do quyết định lộ trình di chuyển cũng như thời điểm xuất phát từ mỗi thành phố. Đặc biệt, bạn có thể xuất phát từ thành phố $1$ vào một thời điểm âm, hoặc dừng lại chờ ở một thành phố nào đó trong một khoảng thời gian mà không đi vào đường cao tốc.
Cho thông tin về các đường cao tốc và hằng số $K$, hãy viết chương trình xác định xem có thể di chuyển từ thành phố $1$ đến thành phố $N$ qua các đường cao tốc hay không, và nếu có thể thì tìm giá trị nhỏ nhất của tổng phí đi đường.
Lưu ý rằng dưới các ràng buộc của bài toán này, có thể chứng minh được rằng nếu có thể di chuyển từ thành phố $1$ đến thành phố $N$ qua các đường cao tốc thì giá trị nhỏ nhất của tổng phí đi đường luôn là một số nguyên.
Ràng buộc
- $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$).
- Tất cả các giá trị đầu vào đều là số nguyên.
Subtask
- ($9$ điểm) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$ điểm) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$ điểm) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$ điểm) $N \le 100$, $M \le 200$, và thỏa mãn ràng buộc sau:
- $N$ là số chẵn, $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$). Ở đây, $\lfloor x \rfloor$ biểu thị số nguyên lớn nhất không vượt quá $x$.
- ($16$ điểm) $N \le 100$, $M \le 200$.
- ($11$ điểm) $N \le 1\,500$, $M \le 3\,000$.
- ($7$ điểm) Không có ràng buộc bổ sung.
Đầu vào
Đầu vào được cho theo định dạng sau:
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
Đầu ra
Nếu không thể di chuyển từ thành phố $1$ đến thành phố $N$ qua các đường cao tốc, hãy in ra -1. Nếu có thể, hãy in ra trên $1$ dòng một số nguyên biểu thị giá trị nhỏ nhất của tổng phí đi đường.
Ví dụ 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
Sơ đồ các thành phố và đường cao tốc của Vương quốc JOI được minh họa như hình dưới đây. Các hình tròn biểu thị thành phố, các mũi tên biểu thị đường cao tốc, và bên cạnh mỗi con đường có ghi giá trị $L_i$ và $C_i$ của con đường đó theo đúng thứ tự này. Chữ số viết bên trong mỗi hình tròn biểu thị chỉ số của thành phố đó.
Nếu di chuyển như sau thì tổng phí đi đường sẽ là $15$:
- Thời điểm $-1$: Xuất phát từ thành phố $1$ và đi đến thành phố $3$. Tốn phí đi đường là $10 + 2 \times |-1| = 12$.
- Thời điểm $0$: Đến thành phố $3$ và lập tức đi đến thành phố $4$. Tốn phí đi đường là $3 + 2 \times |0| = 3$.
- Thời điểm $5$: Đến thành phố $4$.
Vì không tồn tại cách di chuyển nào có tổng phí đi đường nhỏ hơn $15$, nên ta in ra $15$.
Đầu vào mẫu này thỏa mãn các ràng buộc của Subtask $2, 5, 6, 7$.
Ví dụ 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
Chỉ khác Ví dụ $1$ ở giá trị của $K$.
Nếu di chuyển như sau thì tổng phí đi đường sẽ là $9$:
- Thời điểm $-3$: Xuất phát từ thành phố $1$ và đi đến thành phố $2$. Tốn phí đi đường là $2 + 0 \times |-3| = 2$.
- Thời điểm $0$: Đến thành phố $2$ và lập tức đi đến thành phố $3$. Tốn phí đi đường là $4 + 0 \times |0| = 4$.
- Thời điểm $1$: Đến thành phố $3$ và ở lại thành phố $3$.
- Thời điểm $3$: Xuất phát từ thành phố $3$ và đi đến thành phố $4$. Tốn phí đi đường là $3 + 0 \times |3| = 3$.
- Thời điểm $8$: Đến thành phố $4$.
Vì không tồn tại cách di chuyển nào có tổng phí đi đường nhỏ hơn $9$, nên ta in ra $9$.
Đầu vào mẫu này thỏa mãn các ràng buộc của Subtask $1, 2, 5, 6, 7$.
Ví dụ 3
2 1 10 2 1 4 7
-1
Vì không thể di chuyển từ thành phố $1$ đến thành phố $2$ qua các đường cao tốc, nên ta in ra -1.
Đầu vào mẫu này thỏa mãn các ràng buộc của Subtask $2, 5, 6, 7$.
Ví dụ 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
Đầu vào mẫu này thỏa mãn các ràng buộc của Subtask $2, 3, 5, 6, 7$.
Ví dụ 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
Có thể tồn tại nhiều con đường có cùng cặp $(A_i, B_i)$.
Đầu vào mẫu này thỏa mãn các ràng buộc của Subtask $2, 4, 5, 6, 7$.
Ví dụ 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
Đầu vào mẫu này thỏa mãn các ràng buộc của Subtask $5, 6, 7$.