BZOJ 3669 [Noi2014] 魔法森林


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

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


其实就是乱搞= =

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

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

于是就跑的飞起了。

 

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

转载:转载请注明原文链接 - BZOJ 3669 [Noi2014] 魔法森林


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