題目描述: 給定一個無向圖,每個節點有一個價值 values[i],每條邊有通過時間。從節點 0 出發,在總時間不超過 maxTime 的限制下回到節點 0。路徑中每個節點的價值只計算一次(即使多次經過)。求能獲得的最大價值。
解題思路: 關鍵觀察:題目保證每個節點最多有 4 條邊,且 maxTime / (邊的最小時間) 有限,因此 DFS 回溯的搜索樹雖然看似很大,但實際上分支因子受限。
時間複雜度:O(4^(maxTime/minEdge)) — 最壞情況下 DFS 樹的分支因子為 4(每個節點最多 4 條邊),深度為 maxTime / 最小邊權。但因剪枝和時間限制,實際搜索空間遠小於此理論上界。
空間複雜度:O(n + m) — 鄰接表 O(m),Dijkstra 距離陣列 O(n),DFS 遞迴棧和 visited 陣列 O(n)。
1. Build adjacency list.
2. Run Dijkstra from node 0 to compute shortest distances dist[].
3. DFS(node, currentTime, currentValue):
a. If node == 0, update ans = max(ans, currentValue).
b. For each neighbor (v, weight) of node:
- If currentTime + weight + dist[v] <= maxTime:
- If v not visited: mark visited, DFS(v, currentTime+weight, currentValue+values[v]), unmark.
- If v visited: DFS(v, currentTime+weight, currentValue).
4. Start DFS(0, 0, values[0]) with node 0 visited.
5. Return ans.BFS + 狀態壓縮:若節點數少,可用 bitmask 表示已訪問的節點集合,用 BFS 搜索 (node, time, visited_mask) 狀態空間。但節點數可達 1000,bitmask 不可行。
無剪枝純 DFS:省略 Dijkstra 預處理,直接做 DFS 回溯。正確但效率較差,因為會探索許多無法回到起點的路徑。在某些測試案例中可能超時。