如果您已经学过高中数学必修1，或者赶时间，建议直接看四。

一、题意的理解

有$m$条边，每条边的安全系数都是一个百分数。要求找出一条$1\to n$的路径，使得安全系数的乘积最大。

二、乘积的处理

一个处理乘积的技巧——取对数。

对数函数是在高中数学1中讲到的，若$a^t=x$，则$\log_ax=t$。其中$a\in(0,1)\cup(1,+\infty),m,n>0$。

所以很容易看出来（书本上也给出了）对数的运算规律：

$$\because a^{\log_am}=m,a^{\log_an}=n$$$$\therefore a^{\log_am}\cdot a^{\log_an}=mn$$$$\therefore a^{\log_am+\log_an}=mn$$$$\because mn=a^{\log_amn}$$$$\therefore a^{\log_am+\log_an}=a^{\log_amn}$$$$\therefore\log_am+\log_an=\log_amn$$

而此题需要我们求出乘积最大，我们就可以对每条边取自然对数（底为$\mathrm e\approx 2.71828$，在C++中可使用函数log()得到，定义$\ln x=\log_\mathrm ex$），得到新的边权。新边权相加就是原边权相乘取对数。

实际上这个技巧还可以应用在很大的数比大小方面。这个题并不需要。

三、最大的系数

转化为加和关系后，接下来就是求最长路了。最长路的一种不容易出错的方式是把所有边都取相反数，然后跑最短路。此时每次更新的最短路径，实际上就是原图中的最长路径的相反数。而这个题范围也比较小，可以直接floyd解决。

最后再根据定义，对数运算的逆运算是指数运算——若$a^t=x$，则$\log_ax=t$。若$\log_ax=t$，则$a^t=x$。定义域同上。

那么答案就是$\mathrm e^\text{所算出的最短路的相反数}$了。可以用C++中exp()来计算。

四、一句话题解

每条边取对数跑最长路。

五、Code：

#include<cmath>
#include<cstdio>
#include<cstring>
double f[105][105];
int main()
{
    int n,m,u,v,w;
    scanf("%d",&n);
    while(n)
    {
        scanf("%d",&m);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                f[i][j]=1e10;
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d%d",&u,&v,&w);
            f[u][v]=f[v][u]=-log(w/100.0);
        }
        for(int k=1;k<=n;++k)
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j)
                    f[i][j]=f[i][j]<f[i][k]+f[k][j]?f[i][j]:f[i][k]+f[k][j];
        printf("%.6lf percent\n",exp(-f[1][n])*100);
        scanf("%d",&n);
    }
    return 0;
}