題目敘述:https://zerojudge.tw/ShowProblem?problemid=a698

網路上找到的出题人的說明:
NOI年鉴上应该有解题报告。我记得当时给的正解就是<删除>IDA*</删除>二分加A*。
https://www.zhihu.com/question/68307099/answer/261772276
我是这道题目的出题人,下面是我提交给年鉴的解题报告。这道题目数据出了比较严重的问题,当年包括我和验题人在内都没有发现,在这里也给选手们道个歉。
本题考查同学们对最短路以及搜索算法的掌握程度。
本题是一道典型的最短路模型的题目,但是由于所走的路径有限制,若将图根据不同的状态拆点,则点数将是指数级的,显然不能解决N比较大的情况。只有当N比较小的时候可以用(u, set)来表示到达u且以后不能到达文化编号为set集合中的编号的最短路。当N比较大的时候,比较不错的做法是利用经典的搜索算法来计算最短路,这也是标程的做法。
首先,可以二分最优解,设为X,然后用A* search algorithm来验证X是否为一个可行解。A星算法的估价函数选取很重要。比如我们可以选择当前到达的点u到终点T的最短距离作为估价函数,但是显然因为它没有利用已经访问到的节点的信息,并不是一个好的估价函数。一个好的估价函数可以是,从当前节点u到终点T的不经过与已经到达的国家相冲突的国家的最短路的长度。利用二分和A星剪枝,程序可以很快的跑出答案。
其他網友:
众所周知,这道题数据非常水。不考虑约束写一个最短路径算法就有 90 分。然而很多题解的最短路径算法是在松弛时考虑约束条件,然而却没有有关这种方法的正确性证明。而如果用搜索算法(DFS 或者 A*)最后一个测试点会 TLE,许多人采取了对图的转置进行搜索的方法,很显然这是一种针对数据特点的「面向数据编程」。