web analytics

BZOJ1598: [Usaco2008 Mar]牛跑步 Astar

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

分析:

这是K短路的裸题。

A*博客:http://blog.csdn.net/z_mendez/article/details/47057461

这里需要解释一下:

F[n]=g[n]+h[n]

这里F为估值。g表示从头到n的值。这会有很多。

但是h表示从终点到n的距离。这是个精确值。

这样就保证了如果我现在搜索到了n点。我后面的最短路是不需要搜索的。h是现成的。就避免了n后面的搜索。

 

Post a Comment

You must be logged in to post a comment.