BZOJ 1922 [Sdoi2010] 大陆争霸


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

题意:n 个点的有向图,到一个点的前提是保护它的点都去过了,点之间有保护的关系,同时可以派出任意多的人,求 1-n 最短路...


有人说这是分层图最短路... 那就是吧...

记录\({d1}_i\) 为到 i 点的路程时间,\({d2}_i\) 为保护 i 点的点全去过的时间,那么 i 点的真实进入时间为\(max({d1}_i,{d2}_i)\)

跑最短路时按照真实时间更新即可,需要注意的是,一个点可以入队当且仅当保护它的点全去过了

数组的含义在注释里给出了

 

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

转载:转载请注明原文链接 - BZOJ 1922 [Sdoi2010] 大陆争霸


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

标签: , ,