思路与算法

所有边在a∈[0,1]都严格为正，所以最短路可取简单路径。枚举S到T简单路径，每条得到线性费用f(a)=(Σx−Σy)a+Σy。按斜率从大到小排序、同斜率留最低截距，以精确有理交点维护下包络。包络与[0,1]相交的每段都是一条直线，逐段积分即可。

正确性说明

正权环删去会严格减小代价，故枚举简单路径覆盖每个a的最优选择。它们的点态最小值就是所需距离函数。按斜率递减维护时，若新交点不在上一条有效区间右侧，中间线不可能成为最小，可删除；保留的交点递增，恰划分全部下包络。均匀a的期望是该距离函数在[0,1]的积分，分段直线积分精确对应此值。

复杂度

设简单路径条数K≤2^m，DFS总O(n2^m)，排序O(K log K)，包络与积分O(K)，空间O(n+m+K)。n≤10,m≤20为公开缩域，不能声称覆盖原200/400全部图。

易错点

必须先对每天的a取最短，再积分，不能先平均边权。重边是不同选择；S=T空路径为0。交点比较用整数叉乘，最终long double积分；边界0与1要裁剪。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using I = __int128_t;
using D = long double;
struct Edge {
    int v;
    ll x, y;
};
struct Line {
    ll m, b;
};
struct Rat {
    ll n, d;
};
bool le(Rat a, Rat b) {
    return (I)a.n * b.d <= (I)b.n * a.d;
}
int main() {
    int n, m, S, T;
    cin >> n >> m >> S >> T;
    --S;
    --T;
    vector<vector<Edge>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        ll x, y;
        cin >> u >> v >> x >> y;
        --u;
        --v;
        g[u].push_back({v, x, y});
        g[v].push_back({u, x, y});
    }
    vector<Line> a;
    function<void(int, int, ll, ll)> dfs = [&](int u, int mask, ll X, ll Y) {
        if (u == T) {
            a.push_back({X - Y, Y});
            return;
        }
        for (auto e : g[u])
            if (!(mask >> e.v & 1))
                dfs(e.v, mask | (1 << e.v), X + e.x, Y + e.y);
    };
    dfs(S, 1 << S, 0, 0);
    sort(a.begin(), a.end(), [](Line a, Line b) {
        return a.m != b.m ? a.m > b.m : a.b < b.b;
    });
    vector<Line> h;
    vector<Rat> start;
    for (Line z : a) {
        if (!h.empty() && h.back().m == z.m)
            continue;
        Rat r{-(1LL << 60), 1};
        while (!h.empty()) {
            r = {z.b - h.back().b, h.back().m - z.m};
            if (h.size() == 1 || !le(r, start.back()))
                break;
            h.pop_back();
            start.pop_back();
        }
        if (h.empty())
            r = {-(1LL << 60), 1};
        h.push_back(z);
        start.push_back(r);
    }
    D ans = 0;
    for (int i = 0; i < (int)h.size(); i++) {
        D l = max(0.0L, (D)start[i].n / start[i].d),
          r = i + 1 < (int)h.size() ? min(1.0L, (D)start[i + 1].n / start[i + 1].d) : 1.0L;
        if (l < r)
            ans += (r - l) * (h[i].b + (D)h[i].m * (l + r) / 2);
    }
    cout << fixed << setprecision(10) << ans << '\n';
}