题解
【基础】最少的手续费
1 条题解
-
0
#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