1 条题解

  • 0
    @ 2023-12-31 14:07:17
    #include <bits/stdc++.h>
    using namespace std;
    
    const int M=2005;
    int n,m,x,y,z,A,B;
    bool sf[M];
    double Map[M][M],dis[M];
    
    int main(){
       scanf("%d %d",&n,&m);
       for(int i=1;i<=m;i++){
          scanf("%d %d %d",&x,&y,&z);
          Map[x][y]=Map[y][x]=(100.0-z)/100;
       }
       scanf("%d %d",&A,&B);
       for(int i=1;i<=n;i++)
          if(Map[A][i])
          	dis[i]=1*Map[B][i];
       dis[A]=1;
       for(int i=1;i<=n;i++){
          int u=0;
          for(int k=1;k<=n;k++)
             if(sf[k]==false && (u==0 || dis[k]>dis[u]))
                u=k;
          sf[u]=true;
          for(int k=1;k<=n;k++)
             if(Map[u][k] && sf[k]==false){
             	dis[k]=max(dis[k],dis[u]*Map[u][k]);
    			}
       }
       printf("%.8lf",100.0/dis[B]);
       return 0;
    }
    
    • 1

    信息

    ID
    344
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    (无)
    递交数
    4
    已通过
    1
    上传者