主要思路

刚开始想的时候以为是可以直接设置 \(dp[u][0/1]\) 来表示是否已经用掉了一次判断的机会，然而正解其实跟这个差不多，只是用了一种更模式化的做法。

我们考虑从 \(1\) 开始做 DAG DP 求出到达该点的概率，然后反着求一遍期望距离。计算这些概率和期望时务必要留下那些辅助计算用的数组，以便后面枚举每条边时可以快速计算。

枚举一条边 \(u \to v, w\)，重新计算 \(u\) 的概率，然后再加上从 \(1 \to u\) 的期望值，这个东西可以直接用完整的期望减去当前点向下的期望距离而得到。

代码

// BZ3470.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e4 + 200, MAX_E = 1e5 + 200;

int n, m, head[MAX_N], current, deg[MAX_N], idx[MAX_N], itot;
double g[MAX_N], acc[MAX_N], f[MAX_N], acc_w[MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[MAX_E];

void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}

void toposort()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0)
            q.push(i);
    while (!q.empty())
    {
        int u = q.front();
        q.pop(), idx[++itot] = u;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (--deg[edges[i].to] == 0)
                q.push(edges[i].to);
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i <= m; i++)
        scanf("%d%d%d", &u, &v, &w), u++, v++, addpath(u, v, w), deg[v]++;
    toposort(), g[1] = 1;
    for (int i = 1; i <= n; i++)
    {
        int u = idx[i], sum = 0;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            sum += edges[i].weight;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            g[edges[i].to] += 1.0 * g[u] * edges[i].weight / sum;
    }
    memset(deg, 0, sizeof(deg));
    for (int i = n; i >= 1; i--)
    {
        int u = idx[i];
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            acc[u] += edges[i].weight * f[edges[i].to], acc_w[u] += edges[i].weight, deg[u]++;
        if (acc_w[u] > 0)
            f[u] = acc[u] / acc_w[u] + 1;
    }
    double ans = f[1];
    for (int i = n; i >= 1; i--)
    {
        int u = idx[i];
        if (deg[u] <= 1)
            continue;
        double curt = f[1] - g[u] * f[u];
        for (int i = head[u]; i != -1; i = edges[i].nxt)
        {
            double A = acc[u] - edges[i].weight * f[edges[i].to], B = acc_w[u] - edges[i].weight;
            ans = max(ans, curt + g[u] * (A / B + 1));
        }
    }
    printf("%.6lf\n", ans);
    return 0;
}