Deskripsi Masalah
Kerajaan JOI adalah sebuah kerajaan yang terdiri dari $N$ kota, yang dinomori dari $1$ hingga $N$. Di Kerajaan JOI, terdapat $M$ jalan tol satu arah yang menghubungkan kota-kota ini, yang dinomori dari $1$ hingga $M$. Dengan melewati jalan tol $i$ ($1 \le i \le M$), seseorang dapat berpindah dari kota $A_i$ ke kota $B_i$, dan waktu yang dibutuhkan untuk melewatinya adalah $L_i$.
Setiap kali melewati sebuah jalan tol, akan dikenakan tarif tol. Tarif untuk jalan tol $i$ pada saat paling murah adalah $C_i$, tetapi karena semua pekerja di Kerajaan JOI membenci kerja lembur, semakin jauh waktu dari waktu acuan $0$, semakin mahal tarif tolnya. Secara spesifik, jika seseorang berangkat dari kota $A_i$ pada waktu $t$ dan melewati jalan tol $i$, tarif tolnya dinyatakan menggunakan konstanta $K$ sebagai $C_i + K \times |t|$, di mana $|t|$ menyatakan nilai mutlak dari $t$.
Anda yang tinggal di kota $1$ sedang merencanakan perjalanan ke kota $N$ tempat teman Anda tinggal. Karena Anda ingin bepergian dari kota $1$ ke kota $N$ melalui jalan tol, pertama-tama Anda ingin memastikan apakah hal itu mungkin dilakukan, dan jika mungkin, Anda juga ingin mencari berapa total tarif tol minimumnya. Di sini, Anda bebas memilih rute perjalanan maupun waktu keberangkatan dari setiap kota. Secara khusus, Anda boleh berangkat dari kota $1$ pada waktu negatif, atau menghabiskan waktu berdiam di suatu kota tanpa melewati jalan tol.
Diberikan informasi mengenai jalan tol dan konstanta $K$, buatlah program untuk menentukan apakah mungkin bepergian dari kota $1$ ke kota $N$ melalui jalan tol, dan jika mungkin, carilah nilai minimum dari total tarif tol.
Di bawah batasan masalah ini, dapat dibuktikan bahwa jika mungkin bepergian dari kota $1$ ke kota $N$ melalui jalan tol, nilai minimum dari total tarif tol selalu berupa bilangan bulat.
Batasan
- $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$).
- Semua nilai masukan adalah bilangan bulat.
Subsoal
- ($9$ poin) $N \le 100$, $M \le 200$, $K = 0$.
- ($21$ poin) $N \le 100$, $M \le 200$, $L_i \le 20$ ($1 \le i \le M$).
- ($13$ poin) $N \le 100$, $M = N - 1$, $A_i = i$, $B_i = i + 1$ ($1 \le i \le M$).
- ($23$ poin) $N \le 100$, $M \le 200$, serta memenuhi batasan berikut:
- $N$ adalah bilangan genap, dan $\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$ ($1 \le i \le M$). Di sini, $\lfloor x \rfloor$ menyatakan bilangan bulat terbesar yang kurang dari atau sama dengan $x$.
- ($16$ poin) $N \le 100$, $M \le 200$.
- ($11$ poin) $N \le 1\,500$, $M \le 3\,000$.
- ($7$ poin) Tidak ada batasan tambahan.
Masukan
Masukan diberikan dalam format berikut:
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
Keluaran
Jika tidak mungkin bepergian dari kota $1$ ke kota $N$ melalui jalan tol, keluarkan -1. Jika mungkin, keluarkan dalam $1$ baris sebuah bilangan bulat yang menyatakan nilai minimum dari total tarif tol.
Contoh 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
Keadaan kota dan jalan di Kerajaan JOI diilustrasikan pada gambar berikut. Lingkaran melambangkan kota, panah melambangkan jalan, dan di sebelah setiap jalan tertulis nilai $L_i$ dan $C_i$ dari jalan tersebut secara berurutan. Angka yang tertulis di dalam lingkaran menyatakan nomor kota tersebut.
Jika bepergian seperti berikut, total tarif tol menjadi $15$:
- Waktu $-1$: Berangkat dari kota $1$ menuju kota $3$. Memerlukan tarif tol sebesar $10 + 2 \times |-1| = 12$.
- Waktu $0$: Tiba di kota $3$, dan langsung menuju kota $4$. Memerlukan tarif tol sebesar $3 + 2 \times |0| = 3$.
- Waktu $5$: Tiba di kota $4$.
Karena tidak ada cara bepergian dengan total tarif tol kurang dari $15$, keluarkan $15$.
Masukan contoh ini memenuhi batasan Subsoal $2, 5, 6, 7$.
Contoh 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
Hanya nilai $K$ yang berbeda dari Contoh $1$.
Jika bepergian seperti berikut, total tarif tol menjadi $9$:
- Waktu $-3$: Berangkat dari kota $1$ menuju kota $2$. Memerlukan tarif tol sebesar $2 + 0 \times |-3| = 2$.
- Waktu $0$: Tiba di kota $2$, dan langsung menuju kota $3$. Memerlukan tarif tol sebesar $4 + 0 \times |0| = 4$.
- Waktu $1$: Tiba di kota $3$, lalu tetap tinggal di kota $3$.
- Waktu $3$: Berangkat dari kota $3$ menuju kota $4$. Memerlukan tarif tol sebesar $3 + 0 \times |3| = 3$.
- Waktu $8$: Tiba di kota $4$.
Karena tidak ada cara bepergian dengan total tarif tol kurang dari $9$, keluarkan $9$.
Masukan contoh ini memenuhi batasan Subsoal $1, 2, 5, 6, 7$.
Contoh 3
2 1 10 2 1 4 7
-1
Karena tidak mungkin bepergian dari kota $1$ ke kota $2$ melalui jalan tol, keluarkan -1.
Masukan contoh ini memenuhi batasan Subsoal $2, 5, 6, 7$.
Contoh 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
Masukan contoh ini memenuhi batasan Subsoal $2, 3, 5, 6, 7$.
Contoh 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
Mungkin terdapat beberapa jalan yang memiliki pasangan $(A_i, B_i)$ yang sama.
Masukan contoh ini memenuhi batasan Subsoal $2, 4, 5, 6, 7$.
Contoh 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
Masukan contoh ini memenuhi batasan Subsoal $5, 6, 7$.