初始狀態

第 0 步（未行走）：dp[0][v] = 1.0 / N（每點等機率作為起點）

狀態轉移

第 step 步到達 v，必須從 v 的鄰居 u 轉移而來：

dp[step][v] += dp[step-1][u] / degree(u)

其中 u 遍歷 v 的所有鄰居，且 u != x 且 v != x（禁點不參與轉移）。

最終答案

對於禁點 x，答案為 sum(dp[D][v] for v != x)。

完整 AC 程式碼

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 55;
const int MAXD = 10005;

int n, m, d;
vector adj[MAXN];
double dp[MAXD][MAXN];

void solve(int forbidden) {
    // 重置 dp
    for (int i = 0; i <= d; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = 0;
    
    // 初始機率
    for (int j = 1; j <= n; j++)
        dp[0][j] = 1.0 / n;
    
    // DP 轉移
    for (int step = 1; step <= d; step++) {
        for (int v = 1; v <= n; v++) {
            if (v == forbidden) continue; // 禁點不作為目標
            for (int u : adj[v]) {
                if (u == forbidden) continue; // 禁點不作為來源
                dp[step][v] += dp[step-1][u] / adj[u].size();
            }
        }
    }
    
    // 累加答案
    double ans = 0;
    for (int v = 1; v <= n; v++)
        if (v != forbidden) ans += dp[d][v];
    
    printf("%.10f\n", ans);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &m, &d);
        for (int i = 1; i <= n; i++) adj[i].clear();
        
        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        
        for (int x = 1; x <= n; x++)
            solve(x);
    }
    return 0;
}

優化與注意點

• 滾動陣列優化空間：只需 dp[2][MAXN]，因轉移只依賴前一步
• 禁點處理：來源與目標皆排除禁點，等價於在圖中刪除該點及其關聯邊
• 精度要求：輸出 10 位小數，double 足夠
• 時間複雜度：O(N × (N + M) × D) ≈ 50 × 150 × 10000 = 7.5×10⁷，可通過