BZOJ 5049 导航系统

发布于 2017-09-23  269 次阅读


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

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


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

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

若搜不到,bfs 整个图。

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

 


一个非常弱的准退役OIER