BZOJ 5049 导航系统


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

题意:边权为 1 的无向图,k 次询问两点间最短路,数据随机。


考场上写的正解= =,然后惨遭评测机卡常... 早上再交 29s 水过...

考虑到数据随机,即两点间距通常不大,可以认为不超过 8,暴力 meet in the middle,搜 4 层即可。

若搜不到,bfs 整个图。

需要注意的是无解要用并查集判断连通性,无解也 bfs 会 T 死...

 

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

转载:转载请注明原文链接 - BZOJ 5049 导航系统


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

标签: , ,