思路与算法

一条手续费z%的边使资金保留比例(100−z)/100。沿路相乘得p，要让B收到100元，A需100/p，所以应最大化p。把边权概念上变为−ln((100−z)/100)>0，即可用朴素Dijkstra。标程把每个比例分解成不超过97的25个素数的指数，整条路径通过指数相加保存精确值；同时累加经有理区间认证的对数下界作为快速比较。如果两个对数区间分离，直接比较；否则把指数差的正负部分乘成整数，精确比较两个比例。最后按指数构造100/p的分子、分母，长除法输出8位小数。

正确性说明

每条留存率严格在0和1之间，负对数边权严格为正，满足Dijkstra定点标签不会再被后续路径改小的不变量。素因数指数是正有理数的唯一表示；指数相加恰是沿路留存率相乘。整数对数下界L_z满足 L_z≤10⁹·(−ln留存率)<L_z+1，路径区间因此可靠；重叠时退回整数乘积比较，故比较结果始终精确。最大留存率对应最小初始资金，最后有理数长除法得到目标费用。

复杂度

图初始化与朴素Dijkstra扫描均为 O(n²+m)，存图 O(n²)，每个标签25个指数。设一次精确比例比较耗时为 C，比普通整数比较更贵；总上界 O(n²·(25+C)+m)，输出长除法还需 O(D²)，D为结果中间整数数位。指数差最多包含 O(n) 个常数素因子，故 C=O(nD) 的直接上界，常规比较由认证对数区间快速完成。额外整数空间 O(D)，总空间 O(n²+25n+D)。

易错点

多条转账关系连接相同两人时，保留更低手续费；A=B 时答案100。不要把手续费直接相加，也不要把“收到100”误写成“原有100”。n=2000、每边99%手续费的长链可产生4001位费用，直接double会溢出。对数只作有证据的比较加速，最终费用由精确比例计算。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct cpp_int {
    string s;
    bool neg;
    cpp_int(long long v = 0) : s(to_string(v)), neg(v < 0) {
        if (neg)
            s.erase(s.begin());
    }
    void norm() {
        auto p = s.find_first_not_of('0');
        s = p == string::npos ? "0" : s.substr(p);
        if (s == "0")
            neg = false;
    }
    static int cmpabs(const cpp_int &a, const cpp_int &b) {
        if (a.s.size() != b.s.size())
            return a.s.size() < b.s.size() ? -1 : 1;
        return a.s == b.s ? 0 : a.s < b.s ? -1 : 1;
    }
    friend bool operator<(const cpp_int &a, const cpp_int &b) {
        if (a.neg != b.neg)
            return a.neg;
        int c = cmpabs(a, b);
        return a.neg ? c > 0 : c < 0;
    }
    friend bool operator==(const cpp_int &a, const cpp_int &b) {
        return a.neg == b.neg && a.s == b.s;
    }
    friend bool operator!=(const cpp_int &a, const cpp_int &b) {
        return !(a == b);
    }
    friend bool operator>(const cpp_int &a, const cpp_int &b) {
        return b < a;
    }
    friend bool operator<=(const cpp_int &a, const cpp_int &b) {
        return !(b < a);
    }
    friend bool operator>=(const cpp_int &a, const cpp_int &b) {
        return !(a < b);
    }
    cpp_int operator-() const {
        cpp_int r = *this;
        if (r.s != "0")
            r.neg = !r.neg;
        return r;
    }
    friend cpp_int operator+(const cpp_int &a, const cpp_int &b) {
        cpp_int r;
        r.s.clear();
        int carry = 0;
        if (a.neg == b.neg) {
            int i = (int)a.s.size() - 1, j = (int)b.s.size() - 1;
            while (i >= 0 || j >= 0 || carry) {
                int v = carry + (i >= 0 ? a.s[i--] - '0' : 0) + (j >= 0 ? b.s[j--] - '0' : 0);
                r.s += char('0' + v % 10);
                carry = v / 10;
            }
            r.neg = a.neg;
        } else {
            const cpp_int *x = &a, *y = &b;
            if (cmpabs(a, b) < 0)
                swap(x, y);
            int i = (int)x->s.size() - 1, j = (int)y->s.size() - 1;
            while (i >= 0) {
                int v = x->s[i--] - '0' - carry - (j >= 0 ? y->s[j--] - '0' : 0);
                carry = v < 0;
                if (carry)
                    v += 10;
                r.s += char('0' + v);
            }
            r.neg = x->neg;
        }
        reverse(r.s.begin(), r.s.end());
        r.norm();
        return r;
    }
    friend cpp_int operator-(const cpp_int &a, const cpp_int &b) {
        return a + (-b);
    }
    friend cpp_int operator*(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long carry = 0;
        long long z = b;
        if (z < 0)
            z = -z;
        for (int i = (int)a.s.size() - 1; i >= 0; i--) {
            carry += (a.s[i] - '0') * z;
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        while (carry) {
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        reverse(r.s.begin(), r.s.end());
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    friend cpp_int operator/(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long rem = 0, z = b;
        if (z < 0)
            z = -z;
        for (char c : a.s) {
            rem = rem * 10 + c - '0';
            r.s += char('0' + rem / z);
            rem %= z;
        }
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    cpp_int &operator+=(const cpp_int &b) {
        *this = *this + b;
        return *this;
    }
    cpp_int &operator-=(const cpp_int &b) {
        *this = *this - b;
        return *this;
    }
    cpp_int &operator*=(int b) {
        *this = *this * b;
        return *this;
    }
    friend istream &operator>>(istream &in, cpp_int &a) {
        string v;
        if (in >> v) {
            a.neg = v[0] == '-';
            if (v[0] == '-' || v[0] == '+')
                v.erase(v.begin());
            a.s = v;
            a.norm();
        }
        return in;
    }
    friend ostream &operator<<(ostream &out, const cpp_int &a) {
        if (a.neg)
            out << '-';
        return out << a.s;
    }
};

cpp_int fromString(string s) {
    cpp_int a;
    a.neg = !s.empty() && s[0] == '-';
    if (!s.empty() && (s[0] == '-' || s[0] == '+'))
        s.erase(s.begin());
    a.s = s;
    a.norm();
    return a;
}
cpp_int absBig(cpp_int a) {
    a.neg = false;
    return a;
}
cpp_int pow10(size_t n) {
    cpp_int a;
    a.s = "1" + string(n, '0');
    return a;
}
cpp_int operator*(const cpp_int &a, const cpp_int &b) {
    vector<long long> d(a.s.size() + b.s.size());
    for (int i = (int)a.s.size() - 1; i >= 0; --i)
        for (int j = (int)b.s.size() - 1; j >= 0; --j)
            d[i + j + 1] += (a.s[i] - '0') * (b.s[j] - '0');
    for (int i = (int)d.size() - 1; i > 0; --i) {
        d[i - 1] += d[i] / 10;
        d[i] %= 10;
    }
    cpp_int c;
    c.s.clear();
    for (auto x : d)
        c.s += char('0' + x);
    c.neg = a.neg != b.neg;
    c.norm();
    return c;
}
pair<cpp_int, cpp_int> divmod(cpp_int a, cpp_int b) {
    bool sign = a.neg != b.neg, negrem = a.neg;
    a.neg = b.neg = false;
    cpp_int q, rem;
    q.s.clear();
    cpp_int mul[10];
    for (int i = 0; i < 10; ++i)
        mul[i] = b * i;
    for (char z : a.s) {
        rem = rem * 10 + (z - '0');
        int lo = 0, hi = 9;
        while (lo < hi) {
            int mi = (lo + hi + 1) / 2;
            if (mul[mi] <= rem)
                lo = mi;
            else
                hi = mi - 1;
        }
        q.s += char('0' + lo);
        rem -= mul[lo];
    }
    q.neg = sign;
    q.norm();
    rem.neg = negrem;
    rem.norm();
    return {q, rem};
}
cpp_int floorDiv(cpp_int a, const cpp_int &b) {
    auto z = divmod(a, b);
    if (a.neg && z.second != 0)
        z.first -= 1;
    return z.first;
}
cpp_int rootBig(const cpp_int &a) {
    cpp_int root, rem;
    string s = a.s;
    if (s.size() % 2)
        s = "0" + s;
    for (size_t i = 0; i < s.size(); i += 2) {
        rem = rem * 100 + (s[i] - '0') * 10 + s[i + 1] - '0';
        int x = 9;
        while ((root * 20 + x) * x > rem)
            --x;
        rem -= (root * 20 + x) * x;
        root = root * 10 + x;
    }
    return root;
}
string fixedBig(cpp_int rounded, int digits) {
    bool neg = rounded.neg;
    string s = rounded.s;
    while (s.size() <= (size_t)digits)
        s = "0" + s;
    if (digits)
        s.insert(s.size() - digits, ".");
    return (neg ? "-" : "") + s;
}
cpp_int roundedRational(cpp_int a, cpp_int b) {
    bool neg = a.neg != b.neg;
    a.neg = b.neg = false;
    auto q = divmod(a, b);
    if (q.second * 2 >= b)
        q.first += 1;
    q.first.neg = neg && q.first != 0;
    return q.first;
}

const long long LOGS[100] = {
    0,          10050335,   20202707,   30459207,   40821994,   51293294,   61875403,   72570692,
    83381608,   94310679,   105360515,  116533816,  127833371,  139262067,  150822889,  162518929,
    174353387,  186329578,  198450938,  210721031,  223143551,  235722333,  248461359,  261364764,
    274436845,  287682072,  301105092,  314710744,  328504066,  342490308,  356674943,  371063681,
    385662480,  400477566,  415515443,  430782916,  446287102,  462035459,  478035800,  494296321,
    510825623,  527632742,  544727175,  562118918,  579818495,  597837000,  616186139,  634878272,
    653926467,  673344553,  693147180,  713349887,  733969175,  755022584,  776528789,  798507696,
    820980552,  843970070,  867500567,  891598119,  916290731,  941608539,  967584026,  994252273,
    1021651247, 1049822124, 1078809661, 1108662624, 1139434283, 1171182981, 1203972804, 1237874356,
    1272965675, 1309333319, 1347073647, 1386294361, 1427116355, 1469675970, 1514127732, 1560647748,
    1609437912, 1660731206, 1714798428, 1771956841, 1832581463, 1897119984, 1966112856, 2040220828,
    2120263536, 2207274913, 2302585092, 2407945608, 2525728644, 2659260036, 2813410716, 2995732273,
    3218875824, 3506557897, 3912023005, 4605170185};

const int PRIMES[25] = {2,  3,  5,  7,  11, 13, 17, 19, 23, 29, 31, 37, 41,
                        43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
struct Label {
    long long lower;
    int length;
    array<int, 25> e;
    Label() : lower(0), length(0) {
        e.fill(0);
    }
};
bool better(const Label &a, const Label &b) {
    if (a.lower + a.length < b.lower)
        return true;
    if (b.lower + b.length < a.lower)
        return false;
    if (a.e == b.e)
        return false;
    cpp_int num = 1, den = 1;
    for (int i = 0; i < 25; ++i) {
        int d = a.e[i] - b.e[i];
        for (int j = 0; j < abs(d); ++j)
            if (d > 0)
                num *= PRIMES[i];
            else
                den *= PRIMES[i];
    }
    return num > den;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<unsigned char> g((size_t)n * n);
    for (int i = 0; i < m; ++i) {
        int u, v, z;
        cin >> u >> v >> z;
        --u;
        --v;
        auto &a = g[(size_t)u * n + v];
        if (!a || z < a)
            a = z;
        auto &b = g[(size_t)v * n + u];
        if (!b || z < b)
            b = z;
    }
    int A, B;
    cin >> A >> B;
    --A;
    --B;
    array<int, 25> factor[100];
    for (int z = 1; z < 100; ++z) {
        factor[z].fill(0);
        int v = 100 - z;
        for (int i = 0; i < 25; ++i)
            while (v % PRIMES[i] == 0) {
                v /= PRIMES[i];
                ++factor[z][i];
            }
        factor[z][0] -= 2;
        factor[z][2] -= 2;
    }
    vector<Label> d(n);
    vector<bool> reach(n), done(n);
    reach[A] = true;
    for (int it = 0; it < n; ++it) {
        int u = -1;
        for (int i = 0; i < n; ++i)
            if (reach[i] && !done[i] && (u < 0 || better(d[i], d[u])))
                u = i;
        if (u < 0 || u == B)
            break;
        done[u] = true;
        for (int v = 0; v < n; ++v) {
            int z = g[(size_t)u * n + v];
            if (!z || done[v])
                continue;
            Label cand = d[u];
            cand.lower += LOGS[z];
            ++cand.length;
            if (reach[v] && d[v].lower + d[v].length < cand.lower)
                continue;
            for (int j = 0; j < 25; ++j)
                cand.e[j] += factor[z][j];
            if (!reach[v] || better(cand, d[v])) {
                d[v] = cand;
                reach[v] = true;
            }
        }
    }
    cpp_int num = 100, den = 1;
    for (int i = 0; i < 25; ++i)
        for (int j = 0; j < abs(d[B].e[i]); ++j)
            if (d[B].e[i] < 0)
                num *= PRIMES[i];
            else
                den *= PRIMES[i];
    cout << fixedBig(roundedRational(num * pow10(8), den), 8) << '\n';
}