TopCoder

User's AC Ratio

88.2% (30/34)

Submission's AC Ratio

19.8% (49/248)

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

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 (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