題目敘述：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，许多人采取了对图的转置进行搜索的方法，很显然这是一种针对数据特点的「面向数据编程」。