2019年中南大学研究生招生夏令营机试题
发布时间
阅读量：
阅读量
2019年中南大学研究生招生夏令营机试题
-
- 最小花费
最小花费
题目描述
在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。
输入
输入包含多组测试用例。
对于每组样例，第一行输入两个正整数n,m,分别表示总人数和可以互相转账的人的对数。（0<n<=2000）以下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
#include<bits/stdc++.h>
using namespace std;
struct node
{
int to;
double re;
node():to(0),re(0){}
node(int t,double re): to(t),re(re){}
};
double dist[2005];
bool vis[2005];
int n,m,A,B;
void initial()
{
for(int i=0;i<2005;i++)
{
dist[i]=0;
vis[i]=false;
}
}
void dijkstra(int start,vector<vector<node> >&g)
{
for(int i=0;i<g[start].size();i++)
{
int to=g[start][i].to;
double re=g[start][i].re;
dist[to]=re;
}
dist[start]=1; vis[start]=true;
double maxn; int v;
for(int i=0;i<n;i++)//循环n-1次
{
maxn=0;
for(int j=1;j<=n;j++)
if(!vis[j]&&maxn<dist[j])
maxn=dist[j],v=j;
vis[v]=true;
for(int j=0;j<g[v].size();j++)//start-->v-->to
{
int to=g[v][j].to;
double re=g[v][j].re;
if(!vis[to]&&dist[to]<dist[v]*re)
dist[to]=dist[v]*re;
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
initial();
vector<vector<node> >g(n+1);
for(int i=0;i<m;i++)
{
int a,b; double c;
scanf("%d%d%lf",&a,&b,&c);
g[a].push_back(node(b,1-c/100));
g[b].push_back(node(a,1-c/100));
}
scanf("%d%d",&A,&B);
dijkstra(A,g);
printf("%.8lf\n",100/dist[B]);
}
return 0;
}全部评论 (0)
还没有任何评论哟~