HDOJ 4848 Wow! Such Conquering!：DFS + 剪枝求最小到達時間和

題目大意

n≤30 個星球，完全圖給定旅行時間 Txy。從 1 號出發訪問所有星球，到達星球 x 時間 ≤ Deadline[x]。最小化所有星球到達時間之和。不可行輸出 -1。

Floyd + DFS 剪枝

1. 先跑 Floyd 求任意兩點最短路 g[i][j]（可能繞路更快）。
2. DFS 狀態：(當前星球, 累計時間, 當前到達時間, 剩餘星球數)。
3. 剪枝 1：累計時間 + 當前到達時間 * 剩餘數 ≥ 當前最優解 剪枝（樂觀估計）。
4. 剪枝 2：檢查所有未訪問星球的 Deadline 是否 ≥ 下一到達時間，否則剪枝。
5. 嘗試所有未訪問星球作為下一站，遞歸搜索。

核心 DFS

void dfs(int u, int sumTime, int curTime, int left) {
    if (left == 0) { ans = min(ans, sumTime); return; }
    for (int v=1; v<=n; v++) if (!vis[v]) {
        int arrive = curTime + g[u][v];
        if (sumTime + arrive*(left-1) >= ans) continue; // 剪枝1
        bool ok = true;
        for (int j=1; j<=n; j++) if (!vis[j] && deadline[j] < arrive) { ok=false; break; }
        if (!ok) continue; // 剪枝2
        vis[v]=1; dfs(v, sumTime+arrive, arrive, left-1); vis[v]=0;
    }
}

複雜度與效果

• 狀態空間 30! 極大，但雙重剪枝極其有效，實際搜索節點極少。
• Floyd O(n³)=27000 可忽略。
• 全局最優解 ans 初始化為 INF，找不到保持 INF 輸出 -1。