User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

12.3% (26/212)

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

4 4 1 0 3
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

0

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

For Testdata: 0 ~ 3, Score: 11
For Testdata: 4 ~ 7, Score: 24
For Testdata: 9 ~ 10, Score: 32
For Testdata: 0 ~ 12, Score: 33
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 32768 262144
1 1000 32768 262144
2 1000 32768 262144
3 1000 32768 262144
4 1000 32768 262144
5 1000 32768 262144
6 1000 32768 262144
7 1000 32768 262144
8 1200 32768 262144
9 1900 32768 262144
10 1900 32768 262144
11 1200 32768 262144
12 400 32768 262144