全部RE!!!求助!
查看原帖
全部RE!!!求助!
1365062
Deric456楼主2024/8/13 14:58
#include<bits/stdc++.h>
using namespace std;
long double a[2001][2001],dis[2001]={0};//地图:源点到其他各点的距离
bool book[2001]={0};
int main(){
	//转账需要扣手续费,输出A使得B到账100元最少需要的总费用
	//思路:如何转账,让收的钱占转账金额的比例最大
	//设X为A转出的钱,则B收到了Y=X*0.99*0.98
	//我们要求的是转账路径上的每一个占比
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=a[y][z]=(100-z)/100;
	}
	int x,y;
	cin>>x>>y;
	//Dijksrtra
	//先初始化源点到其他各点的距离
	for(int i=1;i<n;i++)
		dis[i]=a[x][i];//dis存的源点x到其他各点的距离
	dis[x]=1;book[x]=true;//自己给自己转钱,不需要手续费
	//遍历距离dis,找距离x最短的点
	for(int i=1;i<=n;i++){
		int k;//存最近的节点下标
		double max=0;
		for(int j=1;j<=n;j++){
			if((book[j]==false)&&(dis[j]>max)){
				k=j;
				max=dis[j];
			}
		}
		book[k]=true;
		if(k==y){
			break;
		}
		for(int j=1;j<=n;j++){
			if(book[j]==false&&dis[k]*a[k][j]>dis[j])
				dis[j]=dis[k]*a[k][j];
		}
	}
	printf("%0.8lf",100.0/dis[y]);
	return 0;
}
2024/8/13 14:58
加载中...