大发体育娱乐在线-大发体育娱乐官方网站-大发体育娱乐登录网址
做最好的网站

最小花费

来源:http://www.dfwstonefabricators.com 作者:编程应用 人气:96 发布时间:2019-09-27
摘要:主题素材背景 标题汇报 在n个人中,某个人的银行账号之间可以互相转载。这几个人之间转化的手续费各差异。给定这几个人里面转化时须求从转账金额里扣除百分之几的手续费,请问

主题素材背景

标题汇报

在n个人中,某个人的银行账号之间可以互相转载。这几个人之间转化的手续费各差异。给定这几个人里面转化时须求从转账金额里扣除百分之几的手续费,请问A起码须求某个钱使得转账后B收到100元。

输入输出格式

输入格式:

先是行输入八个正整数n,m,分别表示总人数和能够相互转载的人的对数。

以下m行每行输入八个正整数x,y,z,表示标号为x的人和标明为y的人里面相互转载要求扣除z%的手续费 。

最后一行输入多个正整数A,B。数据保障A与B之间能够直接或间接地转账。

输出格式:

输出A使得B到账100元起码要求的总成本。正确到小数点后8位。

输入输出样例

输入样例#1:

3 3                                     1 2 12 3 21 3 31 3

输出样例#1:

103.07153164

说明

1<=n<=2000

 1 #include<bits/stdc++.h> 2 using namespace std; 3 double a[2001][2001],dis[2001]={0},minn; 4 int n,m,i,j,k,x,y,f[2001]={0};  5 void init () //定义该函数以处理录入数据 6 { 7     cin>>n/*总人数*/>>m/*可以相互转账的人的对数*/; 8     for(i=1;i<=m;i++) 9     {10         scanf("%d%d",&j,&k);/*录入可以相互转账的两人的序号*/11         scanf("%lf",&a[j][k]);/*将这两人的手续费转存入该数组中*/12         a[j][k]=(100-a[j][k])/100;/*改变手续费的形式(即,将原来的扣除百分比 转换 为剩余百分比)*/13         a[k][j]=a[j][k];/*a传给b的手续费等于b传给a的手续费*/14     }15     cin>>x>>y;/*输入要求计算的两人*/16 }17 void dijkstra(int x)/*定义该函数以确定最小的手续费*/18 {19     for(i=1;i<=n;i++)/*该循环用以将手续费重新赋值给dis数组,f机制用于判断是否以确定出最小值*/20     {21         dis[i]=a[x][i];/*赋值*/22         dis[x]=1;/*x转账给x的手续费为1*/23         f[x]=1;/*x以被确定为本轮中必须要走的最小中转点*/24     }25     for(i=1;i<=n-1;i++)/*该循环用以重新定义从a点转账到b点的手续费*/26     {27         minn=0;/*剩余最少为0*/28         for(j=1;j<=n;j++)/*该循环用以穷举*/29         {30             if(f[j]==0&&dis[j]>minn)/*如果j点并未被确定,并且x转账到j点所能余留的存款最多*/31             {32                 k=j;/*将j点赋值给k点*/33                 minn=dis[j];/*minn用以记录x到j点所需的"最小“手续费,类似于广搜*/34             }35         }36         f[k]=1;/*声明k点被确定*/37         if(k==y)38         {39             break;40         }41         for(j=1;j<=n;j++)42         {43             if(f[j]==0&&dis[k]*a[k][j]>dis[j])/*如果j点没被确定并且x到k点再到j点的所能余留下的存款比x直接转给j点要多*/44             {45                 dis[j]=dis[k]*a[k][j];/*重新定义x到j点的最小手续费*/46             }47         }48     }49 }50 int main()51 {52     init();53     dijkstra;54     printf("%0.8lf",100/dis[y]);55     return 0;56 }

本文由大发体育娱乐在线发布于编程应用,转载请注明出处:最小花费

关键词:

上一篇:没有了

下一篇:没有了

最火资讯