[C++一本通-圖論演算法] 例4-4 最小花費
摘要：
題目描述
在n個人中，某些人的銀行賬號之間可以互相轉賬。這些人之間轉賬的手續費各不相同。給定這些人之間轉賬時需要從轉賬金額里扣除百分之幾的手續費，請問A最少需要多少錢使得轉賬後B收到100元。
輸入輸出格式
輸入格式：
第一行輸入兩個正整數n,m，分別表示總人數和可以互相...
題目描述
在n個人中，某些人的銀行賬號之間可以互相轉賬。這些人之間轉賬的手續費各不相同。給定這些人之間轉賬時需要從轉賬金額里扣除百分之幾的手續費，請問A最少需要多少錢使得轉賬後B收到100元。
輸入輸出格式
輸入格式：
第一行輸入兩個正整數n,m，分別表示總人數和可以互相轉賬的人的對數。
以下m行每行輸入三個正整數x,y,z，表示標號為x的人和標號為y的人之間互相轉賬需要扣除z%的手續費 (z<100)。
最後一行輸入兩個正整數A,B。資料保證A與B之間可以直接或間接地轉賬。
輸出格式：
輸出A使得B到賬100元最少需要的總費用。精確到小數點後8位。
輸入輸出樣例
輸入樣例#1：
3 3
1 2 1
2 3 2
1 3 3
1 3
輸出樣例#1：
103.07153164
資料範圍說明
1<=n<=2000
解題思路
這一題資料較大，所以用Dijkstra，\(O(n^2)\) 實現。由於從一個賬戶轉錢到另外一個賬戶的手續費不同，所以我們視它們為邊的權值。先求出去掉手續費後所遺留下的錢，並在尋找路徑時儘量去找能留下更多錢的路徑（注意在起始點時要給它賦值為1），並將權值相乘，最後拿100除以權值相乘得到的最大值，輸出答案。
實現程式碼
#include <iostream>
#include <cstdio>
using namespace std;
const int M = 2002;
int n,m,a,b,k;
double map[M][M],minn;
double dis[M];
bool vis[M];
void dijkstra(int start)
{
for(int i=1; i<=n; i++)
dis[i]=map[start][i];
vis[start]=true;
dis[start]=1;//必須進行賦值1,因為若進行更改將使用乘法(0*every==0)
for(int i=1; i<n; i++)
{
minn=0;
for(int j=1; j<=n; j++)
if(!vis[j]&&dis[j]>minn)//尋找剩餘金額最大的
minn=dis[j],k=j;
vis[k]=true;
if(k==b) break;//結束標誌
for(int q=1; q<=n; q++)
if(!vis[q]&&dis[q]<dis[k]*map[k][q])
dis[q]=dis[k]*map[k][q];//進行鬆弛
}
}
int main()
{
double z;
scanf("%d%d",&n,&m);
for(int i=1,x,y; i<=m; i++)
{
cin>>x>>y>>z;
map[x][y]=map[y][x]=(100-z)/100;//表示是原金額的百分之幾
}
cin>>a>>b;
dijkstra(a);
printf("%.8lf\n",100/dis[b]);
return 0;
}