bzoj 3669: [Noi2014]魔法森林 动点SPFA

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


由于有两个关键字,不能正常跑spfa,所以我们想办法将一个关键字消除

先把每个边按照第一个关键字从小到大排序,然后一个一个的插入到图中,每插入一条边从这条边的两个端点跑一边spfa

这时候的spfa中的边权只有第二关键字,因为我们认为当前会经过新的边,所以第一关键字最大的一定是当前这个。

每次的答案就是 当前边的第一关键字+spfa的答案,最后取一个min就好了

 

发表评论

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