BZOJ 3669 [Noi2014] 魔法森林

发布于 2017-09-07  161 次阅读


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

题意:双权值单源最短路。


其实就是乱搞= =

对于第一种权值排序,然后依次加入每条边,暴力跑 spfa,如果能更新答案则一定跑了新加入的边,那么随便更新答案。

但是会 T 死= =,怎么办呢,考虑到加入一条边实质上只对这条边的两个端点直接有影响,spfa 不用情况 dis,直接将两个端点丢到队列里跑即可。

于是就跑的飞起了。

 


一个非常弱的准退役OIER