思路与算法

以虚拟起点0代价到达所有点，令d[k][v]为恰好走k条边到v的最小权。初始化d[0][v]=0，逐层扫描全部边松弛。依据Karp最小均值环公式，对每个d[N][v]有限的点计算max_{0≤k<N}(d[N][v]-d[k][v])/(N-k)，再在顶点间取最小。若所有d[N]均无限，图无环，输出指定字符串。

正确性说明

恰好边数DP由最后一条边分类，归纳得到精确最小权。N条边的走法必重复顶点；无此走法等价无环。Karp公式比较长走法与每个短前缀的平均增量，其内层最大值是该终点可支持的循环平均下界，外层最小恰等全图最小环均值；全源0初始化使所有连通部分均被考虑。

复杂度

DP初始化O(N²)，N轮M边松弛O(NM)，公式O(N²)。总O(NM+N²)时间、O(N²+M)空间。权和≤10^10，使用64位，最后比例用long double。

易错点

有向图，可含自环和0权，不能仅从1号点搜索。INF不能参与减法；无环输出大小写和感叹号必须与题面一致。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> e(m);
    for (auto &x : e) {
        cin >> x[0] >> x[1] >> x[2];
        --x[0];
        --x[1];
    }
    const long long INF = 1LL << 60;
    vector<vector<long long>> d(n + 1, vector<long long>(n, INF));
    fill(d[0].begin(), d[0].end(), 0);
    for (int k = 1; k <= n; k++)
        for (auto x : e)
            if (d[k - 1][x[0]] != INF)
                d[k][x[1]] = min(d[k][x[1]], d[k - 1][x[0]] + x[2]);
    long double ans = 1e30;
    for (int v = 0; v < n; v++)
        if (d[n][v] != INF) {
            long double mx = -1e30;
            for (int k = 0; k < n; k++)
                if (d[k][v] != INF)
                    mx = max(mx, (long double)(d[n][v] - d[k][v]) / (n - k));
            ans = min(ans, mx);
        }
    if (ans > 1e29L)
        cout << "PaPaFish is laying egg!\n";
    else
        cout << fixed << setprecision(2) << ans << '\n';
}