2017.1.13【國中部 】普及組模拟賽C組 money 最小花費 題解

原題：

http://172.16.0.132/junior/#contest/show/1363/1

題目描述：

在n個人中，某些人的銀行賬号之間可以互相轉賬。這些人之間轉賬的手續費各不相同。給定這些人之間轉賬時需要從轉賬金額裡扣除百分之幾的手續費，請問A最少需要多少錢使得轉賬後B收到100元。

輸入：

第一行輸入兩個用空格隔開的正整數n和m，分别表示總人數和可以互相轉賬的人的對數。以下m行每行輸入三個用空格隔開的正整數x; y; z，表示标号為x的人和标号為y的人之間互相轉賬需要扣除z%的手續費(z < 100)。最後一行輸入兩個用空格隔開的正整數A和B。資料保證A與B之間可以直接或間接地轉賬。

輸出：

輸出A使得B到賬100元最少需要的總費用。精确到小數點後8位。

樣例輸入：

11

樣例輸出：

9

資料範圍限制：

對于30%的資料， S<=10；

對于100%的資料， S <=1000。

提示：

樣例說明:

取數字4和6，可以得到最大值(1 + 2) + (1 + 2 + 3) = 9。

分析：

某個人X 直接給另一個人Y 轉賬後，假如Y 收到了N元錢，手續費為M% ，那麼X 花費了N／( 1 一M% ）元錢。假如X 和Y 之間可以直接轉賬且手續費為K％的話，我們連接配接一條邊并賦權值為N/ ( 1 一K% ）。為了計算A 最少需要花費多少錢，我們需要找到一條路，使得B 到A 走過的路的權值乘積最小。由于權值都是大于1 的數（總是越乘越大），是以我們可以用Dijks加ra 算法。至于權值乘積最小為什麼也能用最短路算法，這可以用Dijkstra 算法的原理來解釋；

實作：

var
        max:real;
        n,m,i,j,x,y,z:longint;
        dis:array[..]of real;
        v:array[..]of boolean;
        a:array[..,..]of real;
begin
        assign(input,'money.in');reset(input);
        assign(output,'money.out');rewrite(output);
        readln(n,m);
        for i:= to m do
        begin
                read(x,y,z);
                a[x,y]:=(-z)/; a[y,x]:=a[x,y];
        end;
        readln(x,y);
        for i:= to n do dis[i]:=a[x,i];
        dis[x]:=; v[x]:=true;
        for i:= to n- do
        begin
                max:=;
                for j:= to n do
                        if not v[j]and(dis[j]>max) then
                        begin
                                max:=dis[j]; z:=j;
                        end;
                v[z]:=true;
                for j:= to n do
                        if not v[j]and(dis[z]*a[z,j]>dis[j]) then dis[j]:=dis[z]*a[z,j];
        end;
        writeln(/dis[y]::);
        close(input);close(output);
end.