观察到Safe(p)是一个乘积的形式，而我们的迪杰斯特拉算法模板是求和形式。我们可以变形。变成ln（safe(p))=ln(s1)+ln(s2)+...求lnsafe(p) 的最大值。但由于si是小于等于1 的，ln就是小于0的。于是-ln（safeP)=ln(1/s1)+...，要求ln(safeP)的最大值就是求这个式子最小值。于是我们可以把输入的权值变成-ln(1/si)就可以套用迪杰斯特拉求最短路了。最后迪杰斯特拉得到的结果a变成e^(-a)就是结果了。

 

    #include<bits/stdc++.h>
    using namespace std;
    //迪杰斯特拉 
    double dijst(vector<vector<double>> graph,int start,int end)
    {
        int n=graph.size()-1;
        vector<bool> vis(n+1,false);
        vector<double> minDist(n+1,1e100);
        minDist[start]=0;
        for(int i=1;i<=n;i++)
        {
            int cur=start;
            dou...