網頁

2014年4月6日 星期日

POJ 1860 Currency Exchange

題意:
    假設有A,B兩種貨幣,要將A換成B,須透過匯率Rab和手續費Cab,因此實際得到B貨幣=(A-Cab)*Rab元。  
    第一行輸入N, M, S, V,N表示共有N種貨幣(1<=N<=100),M表示底下有M行,每一行有六個數字A,B,Rab,Cab,Rba,Cab,Rab表示A換成B的匯率,Cab表示A換成B需要扣除的手續費,Rba和Cba同理。現在Nick有第S種貨幣V元,題目問Nick透過不斷交換貨幣,然後最後換回第S種貨幣的時候能否大於V元?

想法:
    用SPFA演算法,初始除了Dis[S]=V以外Dis[i]都是0,然後不斷更新Dis的值使其盡可能大,最後判斷Dis[S]是否大於V。