PKU1860-Currency Exchange

題目：http://poj.org/problem?id=1860
有N種不同的貨幣以及M種兌換方法(100,100)，Nick擁有幣種S數量V
這M種兌換方法A B R->C R<-C
A,B表示對應的兩種貨幣編號
R是兌換比率、C是佣金，每次兌換要先扣佣金、再乘比率
(第一對RC是A->B 第二對反之)

問Nick是否有辦法通過某種兌換方法讓他的錢越換越多(當然，要是S種貨幣)


程式碼：http://codepad.org/me3oJM6M
BellmanFord判負環，事實上「匯率兌換無限賺」的這種題目有點太多了…？
我們反向思考定義起點dist[S]=V，其他點的dist是0、dist就是「目前最多能換多少錢」
雖然題目最後說、要換回S種貨幣
事實上還是套用BellmanFord的思想，第V次還能鬆弛成功就是負環
因為只要有了負環錢就無限、而且再怎麼樣都一定能換回本來的S種

對應測資如下(摘自Discuss)

3 2 1 20.0
1 2 1.00 0.00 1.00 1000.00
2 3 1.01 0.00 1.01 0.00
特色是2->1有超高佣金，
如果只是一直鬆弛鬆弛到天荒地老來決定是否有賺
那就會大大的被這種測資卡死