BZOJ 1922 [Sdoi2010] 大陆争霸

发布于 2017-06-15  114 次阅读


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

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


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

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

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

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

 


一个非常弱的准退役OIER