求加法最大值，不求是求相反数的最小值吗，最后取个$-$就好了

spfa 可以ac 代码如下：
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;

const int N = 2010, M = 2e5 + 10;
const double eps = 1e-12;

int h[N], e[M], ne[M], idx;
int n, m, start, target;
bool st[N];
long double dist[N], w[M];

void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa(long double u)
{
memset(st, 0, sizeof st);
memset(dist, -0x3f, sizeof dist);

queue<int> q;
dist[start] = u;
st[start] = true;
q.push(start);

while (q.size())
{
    auto t = q.front();
    q.pop();
    st[t] = false;

    for (int i = h[t]; ~i; i = ne[i])
    {
        int j = e[i];
        long double v = dist[t] * (1.0 - (long double)w[i] / 100.0);
        if (dist[j] < v)
        {
            dist[j] = v;
            if (!st[j])
            {
                st[j] = true;
                q.push(j);
            }
        }
    }
}

if (dist[target] - 100.0 >= eps)
    return true;
else
    return false;

}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m–)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
cin >> start >> target;

long double l = 100.0, r = 10000.0;

while (r - l > eps)
{
    long double mid = (l + r) / 2;
    if (spfa(mid))
        r = mid;
    else
        l = mid;
}

printf("%.12Lf\n", l);

return 0;

}

记录美好生活

#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
const int N = 2020;
int map[N][N];
double dist[N];
int st[N];
int n, m;
int A, B;
double dijsktra(int begin, int end)
{
memset(st, 0, sizeof st);
for (int i = 1; i <= N; i)
dist[i] = 2e10;
dist[end] = 0;
for (int i = 0; i < n - 1; i)
{
int t = -1;
for (int j = 1; j <= n; j)
if (!st[j] && (t == -1 || dist[t] - dist[j] > 1e-8))
t = j;
st[t] = 1;
if (dist[t] == 0)
dist[t] = 100;
for (int j = 1; j <= n; j)
{
if ((100 * dist[t] / (100 - map[t][j])) - dist[j] < 1e-8)
dist[j] = 100 * dist[t] / (100 - map[t][j]);
}
}
return dist[begin];
}
int main()
{
scanf(“%d%d”, &n, &m);
memset(map, 0x3f, sizeof map);
while (m–)
{
int a, b, c;
scanf(“%d%d%d”, &a, &b, &c);
map[b][a] = map[a][b] = min(map[a][b], c);
}
scanf(“%d%d”, &A, &B);
double ans = dijsktra(A, B);
printf(“%.8f”, ans);
return 0;
}
有没有大佬看一下这个代码 为什么wrongTT

#### spfa能求加法最大值

权值有不一定都大于1或者小于1

不确定权值的话就用spfa，spfa只要权值>0就可求。我现在也不大懂了，说的可能会有问题，不要介意。

所以SPFA适用范围广一些，考虑到这道题汇率一定是<1的，那么乘积单调不增，从而我们可以求乘积最大值

可以用Dij求乘积最大值

为什么spfa能求乘积最小和最大啊（

过了很久我也忘了，很久不做题了。不过我感觉这里乘法<1就是加法<0;乘法>1就是加法>0,所以加法中负权边可以求的话，那么乘法>0也可以求。

套用最短路和最长路就能求啊，所以SPFA当然可以求，SPFA的正确性是基于它的松弛操作，所以自然是可以求乘积最小值和乘积最大值的。
考虑Dij为什么不行，因为Dij的最短路算法是贪心的，它贪心的选最小的并且认为这个点不会被更新了，为什么不会被更新了？因为没有负权边，从而你加入优先队列里的dis只会越来越大，毕竟一个数+一个正数一定变大，不可能以后取出来某一个点更新这个点，故我这个点取出来了，就不会再使用。Dij的正确性是基于 “放入优先队列的点的dis是单调的” 这一条件。
所以 对于求最短路，我们要求dis单调递增，即不存在负权边，对于最大乘积，我们要求乘积只允许单调变小，即乘的在0,1之间，对于最小乘积，我们要求乘积必须单调变大，即所有边权都是>=1的
（似乎也不用严格单调，只要不增不减就行了）

@fedfan 不知道这么说您可以理解吗？

感谢大佬！！！我理解了

大佬niu啊

除了nb我不知道说啥