1597 . 變動的過路費
TopCoder
Tags
Description
前情提要。
總之，在某個神奇的世界裡，有N座城市，每座城市從0編號到N-1。有M條雙向道路，每條連接兩個不同的城市。
這個世界很完備(?)，所以不必擔心有兩座城市不能經由這些道路通行的狀況發生。
每條道路上都有兩座收費站，分別對不同方向的人收費。每個收費站（沒錯，同一條道路不同方向過路費也會不一樣）都有一個起始過路費$C$，在第0天時收費就是$C$元。
但特別的是，每座收費站每個方向還有一個費用變量$P\in\mathbb{Z}$，代表每一天結束在下一天開始之前，會把該方向過路費調整$P$元。（正表示過路費調昇、負表示調降、0代表費用一直不變。）
也就是說，第$T$天的過路費為$C+TP$。
你和某個你想陷害的人Q，現在都位於城市$A$。恰好，你們都有一件重要的事情要去城市$B$辦，而截止日期是第$D$天。
也就是說，你們可以在第0天到第$D-1$天的任一天去辦事，但是不能在第$D$天（含）以後才去辦。
而你們這段時間都很閒想待在家裡，所以你們的路線一定是$A\rightarrow B\rightarrow A$。
你預先調查好了每一條道路的過路費資訊，希望能說服Q在某一天去辦事，而你自己也選一天去辦事，使得他比你多付的過路費愈多愈好。
假如說你可以說服Q，並且你一定會走對路，求在最好的策略之下，他至少會比你多付多少元的過路費。
Input Format
輸入的第一行有五個正整數$N, M, A, B, D$，表示這個世界有$N$座城市$M$條道路，你和Q住在城市$A$、你們要去城市$B$辦事，截止日期是第$D$天。
$N \leq 4\times 10^ 4, M \leq 8 \times 10^ 4, D \leq 10^ 9$。
接下來有$M$行，每行有六個數字，$N_1, N_2, C_1, P_1, C_2, P_2$。
$C_1, P_1$表示從$N_1$往$N_2$的收費站的$C$跟$P$值。
$C_2, P_2$表示從$N_2$往$N_1$的收費站的$C$跟$P$值。
$N_1\neq N_2$。
保證在從第0天到截止期限，任何一天任何一條路的過路費都是非負整數，且答案不超過long long範圍。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~3) | $N \leq 100; M \leq 3500$ | 11 |
| 2 (4~7) | $D \leq 200$ | 24 |
| 3 (9~10) | 無限制 | 32 |
| 4 (0~12) | 無限制 | 33 |
Output Format
輸出一個整數，代表在最好的策略下，Q最少要比你多付多少過路費。
Sample Input 1
1 2 5 -1 10 -1
3 2 12 2 7 2
3 0 8 -1 20 -3
1 0 27 -2 3 0
Sample Output 1
Hints
上圖即為範例測資。每一天1→2→3→0→1都只會花掉23元，且不存在少於23元把事情辦完的方法，所以Q可以跟你付相同的過路費。
結果世界在第$D$天的時候滅亡了(?
Problem Source
Problem set / Description by Yihda Yol
建國中學105學年度校內第二次模擬賽 pD
題目改編自Polish Algorithmic Engagements 2006 Final（推廣）
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~3 | 11 |
| 2 | 4~7 | 24 |
| 3 | 9~10 | 32 |
| 4 | 0~12 | 33 |