最小花费-银行转账-图的最短路-超详细解析注释

这篇具有很好参考价值的文章主要介绍了最小花费-银行转账-图的最短路-超详细解析注释。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

最小花费-银行转账-图的最短路-超详细解析注释

【题目描述】
在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

【数据规模】

1<=n<=2000
最小花费-银行转账-图的最短路-超详细解析注释,NOI,蓝桥杯C++,C++基础知识,算法,数据结构,图论文章来源地址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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Java高阶数据结构】图的最短路径问题

    图的最短路径问题! 图的基础知识博客:传送门 最短路径问题: 从在带权图的某一顶点出发,找出一条通往另一顶点的最短路径, 最短也就是沿路径各边的权值总 和达到最小 。 一共会讲解三种算法 Dijkstra算法【单源最短路径】 Bellman-Ford算法【单源最短路径】 改进:SPF

    2024年02月08日
    浏览(35)
  • matlab算法模型——图的最短路径和距离

    目录 一、前言 二、最短路径 1.sqarse创建稀疏矩阵 ​​2.有向图的最短路径         使用graphallshortestpaths函数 使用dijkstra.ma函数(直接引用) 3.无向图的最短路径 使用函数graphallshortestpaths(2021的版本不能用了) 使用shortestpath函数 三、未解决的问题 动态规划——求解某类问题

    2024年02月04日
    浏览(35)
  • DS图—图的最短路径(无框架)迪杰斯特拉算法

    目录 题目描述 AC代码 题目描述 给出一个图的邻接矩阵,输入顶点v,用迪杰斯特拉算法求顶点v到其它顶点的最短路径。 输入 第一行输入t,表示有t个测试实例 第二行输入顶点数n和n个顶点信息 第三行起,每行输入邻接矩阵的一行,以此类推输入n行 第i个结点与其它结点如果

    2023年04月08日
    浏览(38)
  • 【洛谷】P1576 最小花费(最短路--->最长路(通过改边权变定义))

    分析+变动+ACcode 明确定位最短路,其实就是模板加上稍微改动。 变动位置: 1:把权变成汇率(=1.0),即经过了这条边,前就要乘以这这边权,即乘以汇率,拿肯定汇率越高最后到终点的钱多(一个道理终点钱指定,拿汇率越高,最开始的钱就可以拿的越少) 。我们需要在

    2024年02月15日
    浏览(47)
  • C语言数据结构——图的最短路径算法解决实例问题

    一、问题描述 W公司在某个地区有6个产品销售点,现根据业务需要打算在其中某个销售点上建立一个中心仓库,负责向其他销售点提供产品。由于运输线路不同,运输费用也不同。假定每天需要向每个销售点运输一次产品,那么应将中心仓库建在哪个销售点上,才能使运输费

    2024年02月08日
    浏览(46)
  • 数据结构(12)Dijkstra算法JAVA版:图的最短路径问题

    目录 12.1.概述 12.1.1.无权图的最短路径  12.1.2.带权图的最短路径 1.单源最短路径 2.多源最短路径 12.2.代码实现 无权图的最短路径,即最少步数,使用BFS+贪心算法来求解最短路径,比较好实现,此处不做展开讨论。 有权图的最短路径,不考虑权重为负数的情况,因为权重为负

    2024年02月06日
    浏览(45)
  • 详解图的最短路径算法(BFS、Dijkstra、Floyd)(附上图解步骤)

    最短路径分为两种: (1)单源路径:从某顶点出发,到其他全部顶点的最短路径 (2)顶点间的最短路径:任意两个顶点之间的最短路径 最短路径的结果主要有两个方面: (1)顶点之间最短路径的长度 (2)从源顶点到目标顶点的路径 只有边权为 1 时才能用BFS求最短路。

    2024年02月05日
    浏览(52)
  • c语言写邻接矩阵的最短路径的Dijkstra算法(附有详细代码)

    (1) 用dis数组来存储源点1到其他顶点的初始路径,标记1号顶点, 此时dis数组中的值称为最短路径的估计值。 (2) 从dis数组中找出离源起点最近的点2号,以2号顶点为源点进行找最近的顶点。把2号顶点标记,表示已经有最小值。 以2号顶点为源点,看2号顶点有哪些出边,看能不

    2024年02月05日
    浏览(43)
  • 【数据结构】图的应用:最小生成树;最短路径;有向无环图描述表达式;拓扑排序;逆拓扑排序;关键路径

    目录 1、最小生成树 1.1 概念  1.2 普利姆算法(Prim) 1.3 克鲁斯卡尔算法(Kruskal)  2、最短路径 2.1 迪杰斯特拉算法(Dijkstra) 2.2 弗洛伊德算法(Floyd)  2.3 BFS算法,Dijkstra算法,Floyd算法的对比 3、有向无环图描述表达式 3.1 有向无环图定义及特点 3.2 描述表达式 4、拓扑排序

    2024年02月07日
    浏览(46)
  • 领域驱动设计之银行转账:Wow框架实战

    银行账户转账案例是一个经典的领域驱动设计(DDD)应用场景。接下来我们通过一个简单的银行账户转账案例,来了解如何使用 Wow 进行领域驱动设计以及服务开发。 准备转账(Prepare): 用户发起转账请求,触发 Prepare 步骤。这个步骤会向源账户发送准备转账的请求。 校验

    2024年02月05日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包