原文恕删....
刚刚仔细看了一下,只要改一个地方就可以过了
修改过的版本:https://glot.io/snippets/fn534rhbpg
[43:46] 原本是无条件塞pq,不过其实只要处理cost最低的状况就可以了
改这行大概0.910可过
我另外改了[34:40],有以下两个部分
第一个是 j 起始改成 std::max(top.left, weight[top.cur][i]);
相较于原本用continue加上去多少会快一些
另一个是当下一个城市油价比较便宜的时候
其实我们不用再考虑再目前的城市加超过抵达下一个城市所需的油量
因为多出来的部分,一定会比先到下个城市再加油来的贵
这两个修改加起来,可以到0.600
实际上应该可以再缩减,因为最佳的加油油量有固定的模式 (比方说前面提到的这个)
不见得每次都要一点一点去穷举