BNU 25359 Escape Time II：狀態壓縮 DP 求最大寶石收集

BNU 25359 Escape Time II：狀態壓縮 DP 求最大寶石收集

房間數 n ≤ 10，逃生時間 t ≤ 1e6。每個房間有寶石，從起點 s 出發，必須在 t 秒內到達終點 e，求能收集的最大寶石數。若無法按時到達輸出 0。

狀態定義

dp[mask][i] 表示已訪問房間集合為 mask、當前位於房間 i 所需的最短時間。狀態數 2^n * n ≤ 10240，極小。

轉移邏輯

• 初始：dp[1<，其餘設為 INF。
• DFS/BFS 擴展：從狀態 (mask, i) 嘗試走向未訪問的鄰居 j，新時間 nt = dp[mask][i] + dist[i][j]。若 nt ≤ t 且 nt < dp[mask|1<，則更新並繼續搜索。
• 答案：遍歷所有 mask，若 dp[mask][e] ≤ t，計算該 mask 對應的寶石總和，取最大值。