劉汝佳《算法競賽入門經典》UVa 10603 倒水問題：update_ans 函數詳解

問題背景

UVa 10603「倒水」問題：三個容量為 A、B、C 的水壺，初始狀態 (0,0,C)，通過倒水操作達到目標體積 D，求最少倒水總量。代碼中 update_ans 函數令人困惑。

update_ans 函數原碼

void update_ans(const Node& u) {
    for (int i = 0; i != 3; ++i) {
        int d = u.v[i];
        if (ans[d] < 0 || u.dist < ans[d]) ans[d] = u.dist;
    }
}

逐行解析

• u.v[3]：當前三壺水量。
• u.dist：從初態到達此狀態的**累計倒水量**（代價）。
• ans[d]：記錄「某壺水量恰好為 d 時」的**最小倒水量**。初始 -1 表示未達到。
• 循環遍歷三壺，若當前壺水量 d 尚未記錄（ans[d] < 0）或找到更小代價（u.dist < ans[d]），則更新 ans[d]。

核心作用

在 Dijkstra/BFS 搜索過程中，實時記錄「每種具體水量」能以最小代價達到的狀態。 因為題目最終要求：從 D 向下找第一個可達到的水量並輸出其最小代價。ans[] 正是為此服務的「最優代價表」。

為什麼要遍歷三壺？

目標 D 可能出現在**任意一壺**中。搜索時無法預知哪壺會達到 D，故每次出隊即更新三壺對應水量的最優代價。

完整流程回顧

1. 優先隊列按 dist 從小到大擴展狀態（Dijkstra）。
2. 每彈出一狀態 u，調用 update_ans(u) 更新三壺水量的最優代價。
3. 若 ans[d] >= 0（目標水量已達到），可提前終止（因 Dijkstra 保證首次到達即最優）。
4. 最後從 D 向下掃描 ans[]，輸出首個可達水量及其代價。

總結

update_ans 是**動態維護「水量→最小倒水量」映射表**的關鍵函數，體現了 Dijkstra 算法「邊鬆弛、更新最短路」的核心邏輯在狀態空間中的應用。