web analytics

BZOJ1579[Usaco2009 Feb]Revamping Trails 道路升级 分层图最短路

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

分析:

最短路。用dijkstra算法。然而spfa会被卡。

将整个图复制成k+1层.然后优先队列优化dijkstra。

 

Post a Comment

You must be logged in to post a comment.