#include <iostream> #include <iomanip> using namespace std; const int MAXN = 1005; double graph[MAXN][MAXN]; double dist[MAXN]; bool visited[MAXN]; void dijkstra(int start, int n) { // 初始化距离数组和访问标记数组 for (int i = 1; i <= n; ++i) { dist[i] = 0.0; ...

观察到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> ...

思路：深度优先搜索。pre记录了从出发点到当前节点i的安全度。当节点到达目标goal时，更新安全度res。 #include <bits/stdc++.h> using namespace std; double res = 0; void dfs(int i, int goal, vector<vector<double>> &g, vector<bool> &vis, double pre) { if (i == goal) { res = max(res,...