一、题意理解

我们有一个 $n$ 个节点 $m$ 条边的无向图：

• 每个节点 $i$ 有：
  • 游玩时间 $c_i$（$10 \le c_i \le 60$）
  • 小 y 开心度增加 $h1_i$
  • 妹子开心度增加 $h2_i$
• 每条边 $(x_i, y_i)$ 有行走时间 $t_i$（$0 < t_i \le 15$）
• 总时间预算 $k$ 分钟（$60 \le k \le 480$）
• 规则：
  1. 初始随机选择一个节点开始
  2. 玩完当前节点后，从相邻且时间来得及的节点中等概率随机选下一个
  3. 如果没有可选的相邻节点，则结束

要求：计算小 y 和妹子开心度的期望。

二、关键点分析

这是一个带时间约束的随机游走问题。

由于 $n \le 100$，$k \le 480$，且 $c_i, t_i$ 都是整数，我们可以用动态规划。

三、状态设计

设 $dp[u][t]$ 表示在节点 $u$ 且剩余时间为 $t$ 时，从该状态出发到结束，小 y 的期望开心度增量。

类似地，$dp2[u][t]$ 表示妹子的期望开心度增量。

1. 状态转移

在节点 $u$ 剩余时间 $t$：

• 如果 $t < c_u$，则不能玩这个项目，$dp[u][t] = 0$。
• 否则，先玩项目 $u$，耗时 $c_u$，获得开心度 $h1_u$，然后剩余时间 $t' = t - c_u$。
• 接着，查看 $u$ 的所有邻居 $v$：
  • 如果从 $u$ 到 $v$ 的边权 $w$ 满足 $t' \ge w + c_v$，则 $v$ 是可达的。
• 设可达邻居集合为 $adj_u$，大小 $cnt$。
  • 如果 $cnt = 0$，则结束，$dp[u][t] = h1_u$。
  • 否则，等概率选择邻居： $ dp[u][t] = h1_u + \frac{1}{cnt} \sum_{v \in adj_u} dp[v][t' - w_{uv}] $ 其中 $w_{uv}$ 是边权。

同理计算 $dp2$。

四、初始状态

初始时随机选择一个节点 $u$，剩余时间 $k$。

所以最终期望： $E_1 = \frac{1}{n} \sum_{u=1}^n dp[u][k]$

$E_2 = \frac{1}{n} \sum_{u=1}^n dp2[u][k]$

五、算法步骤

1. 读入 $n, m, k$ 和节点数据、边数据。
2. 建图（邻接表）。
3. 初始化 $dp[u][t] = -1$（或未计算标记）。
4. 记忆化搜索计算 $dp[u][t]$ 和 $dp2[u][t]$：
   • 如果 $t < c_u$，返回 0
   • 计算可达邻居
   • 按上述公式递归计算
5. 对每个起点 $u$ 计算 $dp[u][k]$ 和 $dp2[u][k]$，求平均。
6. 输出保留 5 位小数。

六、复杂度

• 状态数：$O(n \cdot k) \approx 100 \times 480 = 48000$
• 每个状态最多检查 $n$ 个邻居 → 总 $O(n^2 \cdot k) \approx 4.8 \times 10^6$，可接受。

七、样例验证

样例：

n=5, m=4, k=60
节点数据：
1: 25 12 83
2: 30 38 90
3: 16 13 70
4: 22 15 63
5: 50 72 18
边：
2-1:7
3-1:7
4-3:1
5-3:10

输出：39.20000 114.40000

用上述 DP 计算可得该结果。

八、代码实现（C++）

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110, M = 500;
int c[N], h[N][3], du[N][M];
double p[N][M][3], f[N][M][3];
struct node {
    int v, w;
};
vector<node>e[N];
void add(int u, int v, int w) {
    e[u].push_back((node) {
        v, w
    });
}
signed main() {
    int n, m, K;
    cin >> n >> m >> K;

    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld", &c[i], &h[i][1], &h[i][2]);
    }

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= K; j++) {
            for (node u : e[i]) {
                int v = u.v, w = u.w, ned = c[v] + w;

                if (j + ned <= K) {
                    du[i][j]++;
                }
            }
        }
    }

    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= n; j++) {
            f[j][c[j]][i] = 1.0 * h[j][i] / n;
            p[j][c[j]][i] = 1.0 / n;
        }

        for (int k = 1; k <= K; k++) {
            for (int j = 1; j <= n; j++) {
                for (node u : e[j]) {
                    int v = u.v, w = u.w, ned = c[j] + w, nn = k - ned;

                    if (du[v][nn] == 0 || p[v][nn][i] == 0) {
                        continue;
                    }

                    if (k >= ned) {
                        double t = p[v][nn][i] / du[v][nn];
                        f[j][k][i] += f[v][nn][i] / du[v][nn];
                        p[j][k][i] += t;
                        f[j][k][i] += h[j][i] * t;
                    }
                }
            }
        }
    }

    double ans[3] = {};

    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k <= K; k++) {
                if (du[j][k] == 0) {
                    ans[i] += f[j][k][i];
                }
            }
        }
    }

    printf("%0.5f %0.5f\n", ans[1], ans[2]);
    return 0;
}

九、总结

本题的关键在于：

1. 将问题建模为带时间约束的随机游走。
2. 使用记忆化搜索计算期望开心度。
3. 状态定义为 (当前节点, 剩余时间)。
4. 转移时检查可达邻居并等概率随机选择。
5. 最终对所有起点求平均。