ID/A/IDA

upd on 10-9：添加了 P10488 Booksort。

本题单三个算法的模板：八数码难题

ID：

全名“迭代加深搜索”。就是利用 bfs 的思路，每次搜索限制深度的 dfs。ID 算法的好处就是第一次搜到的解一定是最优解。

如果你的 bfs MLE 了，不妨来试一发 ID。

A*：

就是每次从优先队列中取出一个估价函数最小的元素，然后更新相邻的状态。

什么是估价函数？

IDA*

字面意思，ID+A*。

有些题 A 能过 IDA 也能过，双向搜索也能过。

K 短路：

注：次短路的题目 A* 能够解决。

不可过的题目如下，仅做录入。

P4467 [SCOI2007] k短路
P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院