例题7-8 (UVa 10603) 正确性

[WangQiuc]

书中提及”上述算法非常直观，正确性却不是显然的“，请问为什么无法严格证明它是正确的？

算法使用priority queue，可以保证每次都pop出dist最小的node u，而每次把u的子节点u2 push进priority queue的时候，u2.dist = u.dist + amount，所以可以严格保证u2.dist > u.dist。

所以当u被pop出，u.v中三个杯子水量的dist (ans[u.v[i]])，如果不是-1 (初始值，没被填充过)，则一定是可达到的最小值，因为u.dist是当前所有node中dist的最小值，而在尚未push进priority queue的state node u2，所有的u2.dist都严格大于u.dist。

此外在update_ans()函数中，
if (ans[d] < 0 || u.dist < ans[d]) ans[d] = u.dist也可以改成if (ans[d] < 0) ans[d] = u.dist，因为被priority queue弹出，第一次出现的水量d，他的dist就是可以达到的最小值，因为之后所有弹出的node的dist都大于当前的dist