最小花费-银行转账-图的最短路-超详细解析注释
【题目描述】
在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问A最少需要多少钱使得转账后B收到100元。
【输入】
第一行输入两个正整数n,m,分别表示总人数和可以互相转账的人的对数。
以下m行每行输入三个正整数x,y,z,表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费 (z<100)。
最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。
【输出】
输出A使得B到账100元最少需要的总费用。精确到小数点后8位。
【输入样例】
3 3
1 2 1
2 3 2
1 3 3
1 3
【输出样例】
103.07153164
【数据规模】文章来源:https://www.toymoban.com/news/detail-808209.html
1<=n<=2000
文章来源地址https://www.toymoban.com/news/detail-808209.html
//【参考代码】
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2000;
double map[N][N];//i点到j点的最小损耗 无向图
double dis[N];//从a点出发到各点的最小损耗
double book[N];//确定最小损耗
int n, m;// 总人数 相互转账人的对数
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
map[i][j] = 10000;//初始值设置的尽可能大
}
}
for(int i=1; i<=n; i++)
{
map[i][i] = 0;
}
//构建图
for(int i=1; i<=m; i++)
{
int x,y,z;
cin>>x>>y>>z;
map[x][y] = z*1.0/100;//百分比除以100
map[y][x] = map[x][y];//无向图
}
int a, b; //a起点 b终点
cin>>a>>b;
//int s = a;
for(int i=1; i<=n; i++)
{
dis[i] = map[a][i];//把a点出发的值赋值到一维数组
}
book[a] = true;//已经使用过
//迪杰斯特拉算法
for(int i=1;i<n; i++)
{
int k = a;
double minv = 10000;//求最小值设置较大初始值
for(int j=1; j<=n; j++)
{
if(dis[j]<minv && book[j]==false)
{
minv = dis[j];//确定最小值
k = j;//最小值对应的下标
}
}
book[k] = true;//用过直接设置true
for(int j=1; j<=n; j++)
{
if(book[j]==false)
{
dis[j] = min(dis[j],dis[k]+(1-dis[k])*map[k][j]);
}
}
}
printf("%.8lf",100/(1-dis[b]));//保留8位小数
return 0;
}
到了这里,关于最小花费-银行转账-图的最短路-超详细解析注释的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!