P1576 最小花费

//https://www.luogu.com.cn/problem/P1576?contestId=96630
//将2转化为0.98
//每次的汇率是相乘的关系
//边的边权就是汇率的乘机因为钱是越乘越少
//要求最少的钱就是求最大的汇率
#include<bits/stdc++.h>
using namespace std;
int n,m;//n是总人数，m是边数
double G[2001][2001];
int a,b;

bool visited[2001];
double dist[2001];
void Dijsktra(int x)
{
   fill(visited+1,visited+1+n,false);
   fill(dist+1,dist+1+n,-1);
   dist[x]=1.0;//最初的本金就是百分之百不变
   for(int i=1;i<=n;i++)
   {
       int u=-1;
       double max=-1;
       for(int j=1;j<=n;j++)
       {
           if(visited[j]==false&&dist[j]>max)
           {
               u=j;
               max=dist[j];//找到最大汇率
           }
       }
       if(u==-1) return;
       visited[u]=true;
       for(int v=1;v<=n;v++)
       {
           if(visited[v]==false&&G[u][v]!=0&&dist[v]<dist[u]*G[u][v])
           {
               dist[v]=dist[u]*G[u][v];
           }
       }
   }
}

int main()
{
   scanf("%d%d",&n,&m);
   fill(G[0],G[0]+2001*2001,0);
   for(int i=0;i<m;i++)
   {
       int u,v;
       double w;
       scanf("%d%d%lf",&u,&v,&w);
       G[u][v]=(100.0-w)/100.0;
       G[v][u]=(100.0-w)/100.0;
   }
   scanf("%d%d",&a,&b);
   Dijsktra(a);
   double ans=100.0/dist[b];
   printf("%.8f",ans);
}