3103 問題 N: 信息學(xué)奧賽一本通T1344-最小花費(fèi)
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 48 解決: 24
題目描述
在n個(gè)人中，某些人的銀行賬號(hào)之間可以互相轉(zhuǎn)賬。這些人之間轉(zhuǎn)賬的手續(xù)費(fèi)各不相同。給定這些人之間轉(zhuǎn)賬時(shí)需要從轉(zhuǎn)賬金額里扣除百分之幾的手續(xù)費(fèi)，請(qǐng)問A最少需要多少錢使得轉(zhuǎn)賬后B收到100元。
輸入
第一行輸入兩個(gè)正整數(shù)n,m，分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對(duì)數(shù)。
以下m行每行輸入三個(gè)正整數(shù)x,y,z，表示標(biāo)號(hào)為x的人和標(biāo)號(hào)為y的人之間互相轉(zhuǎn)賬需要扣除z%的手續(xù)費(fèi) (z<100)。
最后一行輸入兩個(gè)正整數(shù)A,B。數(shù)據(jù)保證A與B之間可以直接或間接地轉(zhuǎn)賬。
輸出
輸出A使得B到賬100元最少需要的總費(fèi)用。精確到小數(shù)點(diǎn)后8位。
樣例輸入
3 3
1 2 1
2 3 2
1 3 3
1 3
提示
【數(shù)據(jù)規(guī)?！?br />
1<=n<=2000