BZOJ 1975 [Sdoi2010] 魔法猪学院


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

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


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

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

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1975 [Sdoi2010] 魔法猪学院


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,