BZOJ 1975 [Sdoi2010] 魔法猪学院

发布于 2017-06-14  191 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1975

题意:求从点 1 到 n 有多少条不同的路径满足路程小于等于 e


有人说这题卡空间,需要手写优先队列... 战战兢兢的码完发现并不卡,虽然 MLE 好几发是别的地方写错...

经典的 K 短路问题,此题 A*算法的估价函数是从当前点到 n 点的距离,那么第 K 次到达就是第 K 短路了...

为什么这么做正确是显然的吧...

 


一个非常弱的准退役OIER