提交时间:2024-08-08 21:45:44

运行 ID: 162922

#include<bits/stdc++.h> using namespace std ; double a[1005][1005],dis[1005],f[1005],maxn; int k; int main(){ int n,m; cin>>n>>m; while(m--){ int x,y,z; cin>>x>>y>>z; a[x][y]=a[y][x]=0.01*(100-z) ; } int x,y; cin>>x>>y; for(int i=1;i<=n;i++){ dis[i]=a[x][i]; } dis[x]=1; f[x]=1; for (int i=1;i<n;i++){ maxn=0; for(int j=1;j<=n;j++){ if(f[j]==0&&dis[j]>maxn){ k=j; maxn=dis[j]; } } f[k]=1; if (!(k-y)){ break; } for(int j=1;j<=n;j++){ if(f[j]==0&&dis[k]*a[k][j]>dis[j]){ dis[j]=dis[k]*a[k][j]; } } } cout<<fixed<<setprecision(8)<<100/dis[y]<<endl; return 0 ; }