5 条题解
-
1
#include<bits/stdc++.h> using namespace std; int n,m,x,y,z,a,b,vis[2001]; double dis[2001],g[2001][2001]; int main() { cin>>n>>m; for(int i=1;i<=m;i++){ cin>>x>>y>>z; g[y][x]=g[x][y]=1-z*0.01; } cin>>a>>b; for(int i=1;i<=n;i++){ dis[i]=g[a][i]; } dis[a]=1; vis[a]=1; for(int i=1;i<n;i++){ double temp=-1; int t=-1; for(int j=1;j<=n;j++){ if(vis[j]==0&&temp<dis[j]){ temp=dis[j]; t=j; } } vis[t]=1; for(int j=1;j<=n;j++){ if(vis[j]==0){ dis[j]=max(dis[j],dis[t]*g[t][j]); } } } double ans=100/dis[b]; printf("%.8lf",ans); return 0; }
信息
- ID
- 2750
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 52
- 已通过
- 23
- 上传者