bzoj 1922: [Sdoi2010]大陆争霸 dijkstra

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


机器人随时可以派出,所以制约我们破坏一个城市的条件只有到达的时间解除保护的时间

令open[i]=第i个点解锁的时间,dis[i]=到达第i个点的最短路

那么破坏这个城市的时间就是max(open[i] , dis[i])

所以我们把这个值塞到堆里,然后跑dijkstra就好了

不要忘记每次将这个点所保护的点减去一层结界,然后将open[i]与当前时间取max

 

发表评论