题面我们先考虑如何让连续的不在房子中的时间尽量短：我们考虑两个有房子的点\(x,y\)，如果\(x\rightsquigarrowu\xrightarrow{w}v\rightsquigarrowy\)这条路径上除了\(x,y\)不存在有房子的点，那么我们可以找到这样一条路径，一定不劣：令\(a,b\)分别为最靠近\(u,v\)的有房