1641 . 貨物運送計劃

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

88.2% (75/85)

Submission's AC Ratio

21.4% (132/616)

Tags

SSC

Description


旭喀國內總共有 N 個城市（編號分別從 1 到 N）和 M 條道路，每一條道路 Ei 都連接著兩個城市 Ai 和 Bi。

其中，由於旭喀國的交通法規，對於每一條道路 Ei 都是單行道，只能從 Ai 前往 Bi，不能逆向行駛。

你現在是一個商人，要將貨物從某個城市 S 運送到另一個城市 T，你要運送的貨物共 1 shik 重（旭喀國的單位，大約等於 SI 公制單位的314.159 kg）。

而在旭喀國內有一個不成文的規定，那就是每條道路 Ei 上都有的商人行會機構，他們會請你順便多帶點東西離開，

至於帶多少的量則視那條路的方便率 Ci 而定，計算方法如下：

「假設你現在帶有 P shik 重的貨物，則你通過那條路後則將會被要求多帶 C×P shik 的物品上路。」


然而如果要在旭喀國內卸貨，就會被要求支付所謂的「物重稅」。（1 Gold per shik）

因此，當然你想要知道最少可以只支付多少物重稅就完成你的送貨行程。

Input Format

本題輸入的測試檔只有單筆測試資料，第一行有四個整數 N、M、S、T，代表旭喀國內的城市數和道路數，以及你送貨行動的起點和終點。

接下來有 M 行，其中的第 i 行會給出道路 Ei 的資訊，包含三個數 Ai、Bi、Ci。

對於所有測試資料，保證 N ≤ 10000，M ≤ 200000，1 ≤ S, T ≤ N。並且對於每一條道路 Ei 保證 1 ≤ Ai, Bi ≤ N，0 < Ci ≤ 231。

（噢不過那麼陰險的商人極少數，c 的平均值事實上約為 1）

Output Format

一個實數代表至少要支付多少物重稅才能完成工作。

以科學記號輸出，保留兩位有效數字，請參考範例輸出。（保證答案 < 101000）

Sample Input 1

3 3 1 3
1 2 1
1 3 4
2 3 2

Sample Output 1

5.00e+000

Hints

Shik How Fat!!

Problem Source

原TIOJ1641 / Skyly & Shik Contest II (Problem B)

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10
Submit
Back to Top