莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. Dijkstra 可以求最短路，亦可求最长路！
2. 就是一道板子题，大家应该都会，就不用我都讲了吧！

#include<bits/stdc++.h>

using namespace std;

const int N = 2010;

int n,m,S,T;
double g[N][N];
double dist[N];
bool st[N];

//可以求最短路，亦可求最长路！
double dijkstra()
{
    dist[S]=1;

    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]<dist[j]))
                t=j;

        st[t]=true;

        for(int j=1;j<=n;j++) dist[j]=max(dist[j],dist[t]*g[t][j]);
    }

    return dist[T];
}

int main()
{
    cin>>n>>m;

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;

        double w=(100.0-c)/100;
        g[a][b]=g[b][a]=w;
    }

    cin>>S>>T;

    printf("%.8lf\n",100/dijkstra());

    return 0;
}