重复的状态，但是时间更优是应当入队的。hash就不是判重了，而是判断是否更优。

这个问题搞死我了。

对于总状态是2的16次方很不理解.如果说是那道毒药解药的题目说总状态可以缩减到

2的10次方,我也知道但是这道题目求的是时间最优,

所以当由两条路径走到的同一状态他们的时间耗的不同,并且时间虽然随运行递增但是有先后,当一个点的最小值更新后由他所开出的子点也会有最小更新,

那这个怎么解决?

无语啊！总状态就2的16次方，直接搜就0MS，随你DFS还是BFS

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 291ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：475ms

dfs+1丁点剪枝..

heap+dijstra~~~

其实还是SPFA好写...

答楼下：

andydemon:我先将补丁按时间从小到大排序，然后宽搜，得到第一个结果就输出，只对了5各点，为什么？？牛们回答下啊

将补丁时间按从小到大排序以后，得到的第一组解未必是最优。因为此题局部的最优不能导致全局最优。

例如

如果当前选择一个时间为1的一个补丁后下一步只能选择到时间为5,10,15的

但如果当前选择一个时间为2的补丁后下一步可以选择的时间就有2,3,4,5的补丁那么组合起来后你贪心选择了时间为1的补丁，下一步最小得到的也只能是1+5=6

而如果你选择了时间为2的补丁，下一步最小值可以得到2+2=4显然优于第一种选择方案。因此你这样的贪心法是不正确的。因此可以采用建边，然后dijkstra来选择最优解

我先来谈谈dijkstra的建边的方法：

如果将错误与正确通过2进制数表示出来，例如用1表示错误,0表示正确，那么最多共有2^15-1=32767个2进制数，最传统的方法就是将这每一个2进制数尝试通过这m个补丁查看是否能得到一个新的2进制数，第i个2进制数通过第mi种补丁得到一个新的j2进制数，那么就将i和j建立起一条边，边的权值即为第mi种补丁所需要的时间，那么将这32767个2进制数都建立起了与之相关的边，再从第1个2进制数出发，例如如果n=15，那么就从111111111111111出发一直到000000000000000为终结进制dijkstra寻找一条最短路径，那么这条最短路径就一定是所要求的最短时间了。前面建边时并不是每一个2进制数都一定有边与之相连，因此可以优化一下比如在dijkstra中加入heap等等，此题就能完美解决。

再谈一谈前面各位所说的HASH+BFS或HASH+DFS的方法：

其实HASH+BFS，HASH在此的作用是判重，简单说也就是记忆化搜索。

因为我们已经知道15位的2进制数一共有32767种，那么从111111111111111出发通过它满足mi个补丁进行BFS扩展出新的结点，然后不断通过队列里的结点再进行扩展，但是这样的话我们可以看出其中很多步骤都是反复进行过。例如先前通过111111111111111扩展出了101101101010111，后面就会从101101101010111点再进行mi种补丁的扩展，但是后来可能扩展出的点通过某种补丁又回到了101101101010111，那么这后来再通过101101101010111扩展时显然和先前用它扩展得到的结点是相同的，因此可以在先得到101101101010111结点时就记录下来，以免后来再进行重复的操作。这也就是我们所说的记忆化搜索。记录这样长的2进制数我们可以采用到HASH表，每扩展出的点都记录到HASH表，以后如果又扩展到HASH表中存在的元素，那么就不采用，因此这样看来最多只需要扩展出32767个结点，就可以得到题目所要求的最优解。

HASH+DFS方法于HASH+BFS方法类似。在此就不再多说

位运算+bfs

后来发现可以用最短路（DIJ+heap或spfa均可），但不能存边，而要实地生成边。

数据太弱。我乱减了一下，BFS，然后……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

由于考虑到HASH表只能记录打补丁后的时间而不能判断重复，我开了20W的搜索表

估计题目没出现太多的重复（而且更优）的情况。

我先将补丁按时间从小到大排序，然后宽搜，得到第一个结果就输出，只对了5各点，为什么？？牛们回答下啊

二进制表示，建图，有向边，权为时间，Dijkstra+heap...

我想知道拿哈希表判重什么，哪位大牛来给解释一下~~

我怎么觉得这道题的重复情况用boolean更快吧？

Dijkstra + Heap王道

哪位大牛能说说怎么Dijkstra啊？

不会超时吗

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

哈哈，原来深搜也可以这么快。

不明白,为什么加了排序就过!!!!!!!!!!

汗~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

位处理真是个好东西,现在判断可行和转移状态都只要O(1)了...

if (s and cu[i]=cu[i]) and (s or cv[i]=cv[i]) then ...

j:=s and rv[i] or ru[i]; ...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

hush表+广搜

0ms通过。。爽

终于.....

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 634ms

├ 测试数据 10：答案正确... 619ms

用楼上的2进制表示节点（最多65536个），用“补丁”作边（由于边可能很多，所以只能在检查节点的时候 看该节点对应的状态能用那些补丁），然后Dijstra就行了。（我用堆优化的那种过了，但是看这效率大概不用堆也能过）

编译通过...

测试数据1：答案正确... 0ms

测试数据2：答案正确... 0ms

测试数据3：答案正确... 0ms

测试数据4：答案正确... 0ms

测试数据5：答案正确... 0ms

测试数据6：答案正确... 0ms

测试数据7：答案正确... 0ms

测试数据8：答案正确... 0ms

测试数据9：答案正确... 41ms

测试数据10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：82ms