TopCoder

User's AC Ratio

100.0% (17/17)

Submission's AC Ratio

19.6% (27/138)

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

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

Sample Output

5.00e+000

Hints

Shik How Fat!!

Problem Source

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

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 65536
1 3000 65536 65536
2 3000 65536 65536
3 3000 65536 65536
4 3000 65536 65536
5 3000 65536 65536
6 3000 65536 65536
7 3000 65536 65536
8 3000 65536 65536
9 3000 65536 65536