当前位置: 代码迷 >> 综合 >> WUST 1934 最小花费(最短路+迪杰斯特拉)
  详细解决方案

WUST 1934 最小花费(最短路+迪杰斯特拉)

热度:77   发布时间:2023-11-17 14:33:04.0

1934: 最小花费

Time Limit: 1 Sec   Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 8   Accepted: 6
[Submit][Status][Web Board]

Description

    在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问A最少需要多少钱使得转账后B收到100元。

Input

多组测试数据。
第一行输入两个正整数n,m,分别表示总人数和可以互相转账的人的对数。1<=n<=2000
以下m行每行输入三个正整数x,y,z,表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费 (z<100)。
最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。

Output

    输出A使得B到账100元最少需要的总费用。精确到小数点后8位。

Sample Input 


3 3
1 2 1
2 3 2
1 3 3
1 3


Sample Output

103.07153164



[Submit][Status][Web Board]

题解:

由于是点较多,所以选择迪杰斯特拉算法,题目是迪杰斯特拉算法的变形,松弛的条件变了,算是最短路练习吧

代码:

#include<iostream>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
using namespace std;
const int INF=10086111;
int p[2005][2005];//保存路径
double dis[2005];//起始点点到其他点的距离
int vis[2005];//判断是否遍历的数组
int main()
{int i,j,k,n,m,x,y,d;while(scanf("%d%d",&n,&m)!=EOF){memset(vis,0,sizeof(vis));for(i=1;i<=n;i++){for(j=1;j<=n;j++)p[i][j]=INF;//开始初始化}for(i=0;i<m;i++){scanf("%d%d%d",&x,&y,&d);p[x][y]=d;p[y][x]=d;}scanf("%d%d",&x,&y);for(i=1;i<=n;i++){if(p[x][i]==INF)//要特判是否有通路dis[i]=INF;elsedis[i]=100*100/(double)(100-p[x][i]);}vis[x]=1;//标记for(i=1;i<n;i++){int key;double minn=INF;for(j=1;j<=n;j++){if(!vis[j]&&dis[j]<minn)//找一个最小的且没有标记过的{key=j;minn=dis[j];}}vis[key]=1;//标记for(j=1;j<=n;j++){if(p[key][j]==INF)//很重要continue;if(minn*100/(double)(100-p[key][j])<dis[j])//松弛操作的条件变化了,因为算路径长度的方法变了dis[j]=minn*100/(double)(100-p[key][j]);}}printf("%.8lf\n",dis[y]);}return 0;
}


  相关解决方案