bzoj 1880: [Sdoi2009]Elaxia的路线 SPFA

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


因为点数只有1500个,所以我们可以在跑完4遍spfa之后直接n^2的去枚举两个点,判断这两个点是否都在最短路中,如果是,我们就可以O(1)的算出这两个点之间的距离,最后取一个max就好了

 

bzoj 1880: [Sdoi2009]Elaxia的路线 SPFA》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注