top1编程
← 返回题目
题解

【基础】最少的手续费

1 条题解

  • 0
    @ 2026-7-29 0:19:07
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int m,n,x,y;
    bool f[2001];
    double a[2001][2001],d[2001]={0},mi,s;
    void init();
    void work(int k);
    int main()
    {
    	init();
    	work(x);
    	s=100/d[y];
    	printf("%0.8lf",s);
    	return 0;
    }
    void init()
    {
    	cin>>n>>m;
    	for(int i=0;i<m;++i)
    	{
    		cin>>x>>y;
    		cin>>a[x][y];
    		a[x][y]=(100-a[x][y])/100;
    		a[y][x]=a[x][y];
    	}
    	for(int i=1;i<=n;++i)
    	{
    		f[i]=true;
    	}
    	cin>>x>>y;
    }
    void work(int k)
    {
    	for(int i=1;i<=n;++i)
    	{
    		d[i]=a[k][i];
    	}
    	d[k]=1;
    	f[k]=false;
    	for(int i=1;i<=n-1;++i)
    	{
    		mi=0;
    		for(int j=1;j<=n;++j)
    		{
    			if(f[j]&&d[j]>mi)
    			{
    				k=j;
    				mi=d[j];
    			}
    		}
    		f[k]=false;
    		if(k==y)
    		{
    			break;
    		}
    		for(int j=1;j<=n;++j)
    		{
    			if(f[j]&&d[k]*a[k][j]>d[j])
    			{
    				d[j]=d[k]*a[k][j];
    			}
    		}
    	}
    }
    
    • 1