UVa 10603 Fill倒水问题单元最短路Dijkstra

题目链接：Fill
题目描述：

设有三个容器，其容量分别为a, b, c，初始时仅有第三个容器装有c单位的液体。每次操作允许将一个容器中的液体倒入另一个尚未装满的容器中。在倒水过程中，除非某一容器被完全排空或被完全注满，否则倒水动作将持续进行。例如，若三个容器的容量分别为3, 3, 5，当第三个容器中的液体达到满载状态时，将其倒入第二个容器后，三个容器内的液体量变为：0, 3, 2。如果再次将第三个容器中的液体倒入第一个容器中，则此时各容器内的液体量为：2, 3, 0。现在给定一个数值d，要求找到一种方式使得某一个容器中恰好含有d单位的液体；若无法实现该目标，则需寻找一个尽可能接近d且小于d的数值d'，并确保在此过程中所消耗的总倒水量最少。

题解：

我们可以将每个可能的三个容器状态视为图中的一个节点，并将每一次倒水操作视为从一种状态到另一种状态的转移过程。这种转移可以看作是两个节点之间存在一条具有特定权值（即此次倒出的水量）的有向边。因此，本题实际上可以转化为如下问题：从初始状态[0, 0, c]出发，在所有可能的状态中寻找最接近目标值d的那个节点，并确保路径上的总倒水量最小。由于这是一个单源最短路径问题且不存在负