解題說明
Maximum Path Quality of a Graph
題目描述： 給定一個無向圖，每個節點有一個價值 values[i]，每條邊有通過時間。從節點 0 出發，在總時間不超過 maxTime 的限制下回到節點 0。路徑中每個節點的價值只計算一次（即使多次經過）。求能獲得的最大價值。
解題思路： 關鍵觀察：題目保證每個節點最多有 4 條邊，且 maxTime / (邊的最小時間) 有限，因此 DFS 回溯的搜索樹雖然看似很大，但實際上分支因子受限。
- 先用 Dijkstra 或 BFS 從節點 0 計算到所有節點的最短距離，用於剪枝：若當前時間 + 從當前節點回到 0 的最短時間 > maxTime，則剪掉。
- DFS 回溯：維護 visited 集合記錄已計入價值的節點。
- 每到達一個未計入的節點，加入其價值。
- 當回到節點 0 時，更新最大價值。
- 向鄰居擴展時檢查時間限制和最短距離剪枝。
C++ 解法
複雜度分析
時間複雜度：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 回溯。正確但效率較差，因為會探索許多無法回到起點的路徑。在某些測試案例中可能超時。
延伸思考
- 若圖是有向圖，Dijkstra 剪枝需要如何調整？
- 若每個節點的價值在每次訪問時遞減（如第 k 次訪問獲得 value/k），如何修改演算法？
- 若要求輸出具體的最優路徑而非只是最大價值，需要記錄哪些額外資訊？