回分類題庫
h123: A.可魚果運輸問題
關鍵字: NPSC 2013 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 25 Times / 24 Users | Submit : 89 Times / 27 Users | Accepted rate : 89%
題目加入時間 : 2014-09-16 09:39

Content: 简体中文

你是一個販賣可魚果的廠商。最近有一隻富有的大可魚花了他五百一十四分之一百四十五的財產訂購了大量的可魚果,導致你原本的物流機制出了些問題。無計可施的情況下,你只得把運輸可魚果的工作交給可魚國內有名的墨魚運輸公司處理。

然而,正如墨水一般黑,墨魚運輸公司雖然運輸量大、使命必達,但墨魚運輸公司所開的價碼異常昂貴。俗話說,賠錢的生意沒人作,作為一個商人,你為了避免利潤受到過多的壓縮,決定參與規劃運輸路線,使得運輸成本降到最低。

墨魚運輸公司提供了許多運輸方案,每個方案 Pi 會從一個固定的起始城市 Ai 運送東西到另一個固定的終點城市 Bi,每運輸一箱的可魚果,你就必須付給墨魚運輸公司 Ci 可魚幣。另外,若兩個方案的終點與起點相接,則可以不花任何額外費用的將貨物轉過去。不過由於你的運輸量太大了,墨魚運輸公司決定祭出優惠,若用方案 Pi 運輸了超過 Di 箱的可魚果,多出來的部份每箱改收優惠價 Ci 可魚幣。

你原本是隻數學挺好的可魚,但不幸的,你前些日子去東北方的日升之國談生意時感冒了,無法進行複雜的運算。你好奇運輸費究竟可以壓到多低呢? 

Input:

輸入的第一行有一個正整數 T (T ≤ 20),代表測試資料的組數。

每筆測資的第一行有五個正整數 N (N ≤ 100), M (M ≤ N(N −1)), S, E (1 ≤ S, E ≤ N), F (F ≤ 109),各一個空白隔開。N 代表可魚國內有幾個城市,M 代表墨魚運輸公司提供幾種運輸方案。S, E 分別代表你的工廠所在的城市以及你所要送去的城市。F 代表那隻富有的大可魚訂購了多少箱的可魚果。

接下來 M 行,每行有五個正整數 Ai, Bi (1 ≤ Ai, Bi ≤ N), Ci, Di (Di ≤ 109), Ci (Ci ≤ Ci ≤50216),意思如同敘述中所說。 

Output:

對每筆測試資料請輸出一行,包含一個整數代表至少需要付給墨魚運輸公司多少可魚幣。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
4 4 1 4 1
1 2 1 1 1
2 4 5 1 3
1 3 1 1 1
3 4 6 1 1
4 4 1 4 2
1 2 1 1 1
2 4 5 1 3
1 3 1 1 1
3 4 6 1 1
2 1 1 2 999999999
1 2 50216 1000 50216

Sample Output :

6
9
50215999949784

Hint :

[註腳] 其實你原本是隻滿耐寒的可魚,但你在一個僅有 2C 的雨天中只穿了一件短袖棉 T 與外套,就感冒了。並且因為感冒,思路不清,你在日升之國的生意就給死對頭 0perasan 搶走了。

Author :

NPSC 2013 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum