1344:最小花费(最短路)---信息学奥赛一本通

news/2024/12/22 22:18:23/

【题目描述】

在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

解析:

        总计的手续费费率越小,则花钱越多,所以我们需要找到最大的“路线”,即最远路。

#include<bits/stdc++.h>
using namespace std;
const int N=2000+5;
const int INF=0x3f3f3f3f;
int n,m,ts,te;
struct edge{int to,w;};
struct node{int id;double dis;bool operator<(const node& a)const{return a.dis>dis;}
};
vector<edge>e[N];
void solve(){double dis[N];int done[N];priority_queue<node>q;for(int i=1;i<=n;i++) dis[i]=0,done[i]=0.0;q.push({ts,1});dis[ts]=1;while(q.size()){node u=q.top();q.pop();if(done[u.id]) continue;done[u.id]=1;for(int i=0;i<e[u.id].size();i++){edge x=e[u.id][i];if(done[x.to]) continue;if(dis[x.to]<(100-x.w)/100.0*u.dis){dis[x.to]=(100-x.w)/100.0*u.dis;q.push({x.to,dis[x.to]});}}}printf("%.8lf",100.0/dis[te]);
}
int main(){scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);e[a].push_back({b,c});e[b].push_back({a,c});}scanf("%d%d",&ts,&te);solve();	return 0;
}

http://www.ppmy.cn/news/1001882.html

相关文章

许战海咨询方法论系列白皮书在京隆重发布

新时代&#xff0c;面对剧烈变化的竞争环境&#xff0c;企业如何实现结构性增长&#xff1f; 7月31日&#xff0c;许战海咨询最新研究成果——《主品牌进化战略》、《第二招牌增长战略》、《链主品牌&#xff1a;制造业的竞争之王》三本核心方法论白皮书&#xff0c;重磅发布。…

数据结构----c语言复习

数据结构----c语言复习 一.类型 1.类型的种类 char 1个字节 范围-128~127 short 2个字节 范围-32768~32767 int 4个字节 范围-2147483648~2147483647 long 4个字节 范围-2147483648~2147483647 float 4个字节 有效位为6~7位 float 8个字节 有效位为15~16为 unsigned c…

HandleAllMethodExceptions

目录 1 HandleAllMethodExceptions 1.1 OnMethodExecutedAsync 1.2 OnMethodExecuting 1.3 OnMethodExecutingAsync HandleAllMethodExceptions using System; using System.Threading.Tasks; namespace Flatwhite.Core.Tests.Attributes { public class HandleAl…

【设计模式——学习笔记】23种设计模式——命令模式Command(原理讲解+应用场景介绍+案例介绍+Java代码实现)

文章目录 案例引入介绍基础介绍登场角色 案例实现案例一实现 案例二介绍实现拓展 命令模式在JdbcTemplate源码中的应用总结文章说明 案例引入 有一套智能家电&#xff0c;其中有照明灯、风扇、冰箱、洗衣机&#xff0c;这些智能家电来自不同的厂家&#xff0c;我们不想针对每一…

微信小程序使用mp-html遇到的问题并解决

1、在本地配置寻找勾选使用npm 查了之后发现2023了 不需要勾选了 默认使用npm 2、在微信小程序编辑器左上角的 工具-->构建npm 然后就报错了 于是搜索到以下的内容&#xff1a; 没有找到可以构建的NPM包&#xff0c;请确认需要参与构建的npm都在 miniprogramRoot 目录内 -…

十分钟python入门 日期时间

1.Python 日期 Python 中的日期不是其自身的数据类型&#xff0c;但是我们可以导入名为 datetime 的模块&#xff0c;把日期视作日期对象进行处理。 1.1 导入 datetime 模块并显示当前日期&#xff1a; import datetime#导入 datetime 模块并显示当前日期&#xff1a; x da…

【css】css设置表格样式-边框线合并

<style> table, td, th {border: 1px solid black;//设置边框线 }table {width: 100%; }td {text-align: center;//设置文本居中 } </style> </head> <body><table><tr><th>Firstname</th><th>Lastname</th><t…

右值引用带来的效率提升(C++11)

文章目录 一.左值引用和右值引用二.C11区分左值和右值的语法设计意义--对象的移动构造和移动赋值场景分析1:C11之前C11之后 场景分析2:函数std::move右值引用的广泛使用 三.引用折叠 一.左值引用和右值引用 左值:可以取到地址的对象(可以出现在赋值符号的左边),对左值的引用称…