Problem : 9 - 大麥克的世界旅行

Problem Statistics

Solved Member: 49　　Submission: 581　　User Tried: 54

Statement:

Bessie正在牛學院(cowllege)學習她最愛的課程：總體經濟學。

為了準備她的畢業論文，她要發表一篇關於國家之間匯率的研究報告。

為了使得她的報告更加生動，她將要展示世界各地的大麥克的價格(雖然她非常討厭這些不健康的垃圾食品)。給出大麥克在某個國家的價格和一些國家貨幣之間的匯率，Bessie想知道一個大麥克在某個國家的最便宜的價格。

下面看個例子：
* 一個大麥克在美國售價60美元。
* 美元對加拿大元的的匯率是0.2，也就是1美元可以兌換0.2加拿大元。
* 美元對英鎊的匯率是5.00，也就是1美元可以兌換5.00英鎊。
* 英鎊對加拿大元的匯率是0.5，也就是1英鎊可以兌換0.5加拿大元。
* 加拿大元對美元的匯率是5.00，也就是1加拿大元可以兌換5.00美元。

Bessie想要找到在加拿大購買一個大麥克最便宜的方式（通過貨幣的流通與兌換）。

以下有兩種方式：
* 從美元直接兌換加拿大元，這樣一個大麥克價值 60 美元 * 0.2 = 12 加拿大元。
* 從美元兌換成英鎊，再有英鎊兌換為加拿大元，這樣一個大麥克價值 60 美元 * 5 英鎊 * 0.5 加元 = 150 加元。

Bessie會選擇前一種兌換方式，這樣她購買一個大麥克可以只付12加元。
Bessie在研究N (1 <= N <= 2,000) 個國家，編號為1...N。她列出了M(1 <= M<= 25,000)種兌換方式和相對應的匯率e_ij (0.1 < e_ij <= 10)，表示國家i和j的貨幣的兌換比例是e_ij(是單向的)。

Task:

給出一個實數V (1 <= V <= 1,000,000,000,000)，表示一個大麥克在A國(1 <= A <= N)的售價。
你能夠幫助她找到一種方式使得一個大麥克在B國(1 <= B <= N; B != A)的售價儘可能少嗎？
如果售價沒有最小值，輸出0。保證最終答案如果不是0，一定在1到10^15之間。保證任何國家的貨幣可以兌換為任何另一個國家的貨幣。

Input:Output:

* 第1行： 5個空格分隔的數字： N, M, V, A, B
* 第2...M+1行：三個空格分開的數字： i, j, e_ij

如果不存在最小值，為0。否則是一個正數，請你四捨五入到整數位。

Sample Input:Sample Output:

3 4 60 1 2
1 2 0.2
1 3 5
3 2 0.5
2 1 5

Source:

USACO 2010 Dec. Gold

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	2000ms	65536kb
1	2000ms	65536kb	10
2	2000ms	65536kb	10
3	2000ms	65536kb	10
4	2000ms	65536kb	10
5	2000ms	65536kb	10
6	2000ms	65536kb	10
7	2000ms	65536kb	10
8	2000ms	65536kb	10
9	2000ms	65536kb	10
10	2000ms	65536kb	10