在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。
1934: 最小花费
Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lldSubmitted: 8 Accepted: 6
[Submit][Status][Web Board]
Description
Input
多组测试数据。
第一行输入两个正整数n,m，分别表示总人数和可以互相转账的人的对数。1<=n<=2000
以下m行每行输入三个正整数x,y,z，表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费 (z<100)。
最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。
Output
输出A使得B到账100元最少需要的总费用。精确到小数点后8位。
Sample Input
3 3
1 2 1
2 3 2
1 3 3
1 3Sample Output
103.07153164题解：
由于是点较多，所以选择迪杰斯特拉算法，题目是迪杰斯特拉算法的变形，松弛的条件变了，算是最短路练习吧
代码：
#include<iostream>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
using namespace std;
const int INF=10086111;
int p[2005][2005];//保存路径
double dis[2005];//起始点点到其他点的距离
int vis[2005];//判断是否遍历的数组
int main()
{int i,j,k,n,m,x,y,d;while(scanf("%d%d",&n,&m)!=EOF){memset(vis,0,sizeof(vis));for(i=1;i<=n;i++){for(j=1;j<=n;j++)p[i][j]=INF;//开始初始化}for(i=0;i<m;i++){scanf("%d%d%d",&x,&y,&d);p[x][y]=d;p[y][x]=d;}scanf("%d%d",&x,&y);for(i=1;i<=n;i++){if(p[x][i]==INF)//要特判是否有通路dis[i]=INF;elsedis[i]=100*100/(double)(100-p[x][i]);}vis[x]=1;//标记for(i=1;i<n;i++){int key;double minn=INF;for(j=1;j<=n;j++){if(!vis[j]&&dis[j]<minn)//找一个最小的且没有标记过的{key=j;minn=dis[j];}}vis[key]=1;//标记for(j=1;j<=n;j++){if(p[key][j]==INF)//很重要continue;if(minn*100/(double)(100-p[key][j])<dis[j])//松弛操作的条件变化了，因为算路径长度的方法变了dis[j]=minn*100/(double)(100-p[key][j]);}}printf("%.8lf\n",dis[y]);}return 0;
}