4885专题

HDU 4885 TIANKENG’s travel(几何bfs)

HDU 4885 TIANKENG’s travel 题目链接 题意:给定起点,终点,和一些加油站,要求路过最少的加油站到终点,两点距离必须小于L 思路:先建图,建图时把两点中间没有点,并且距离能到达的建一条长度1的边,那么问题就是如何判断中间没有点,先把所有点按x排序,然后每次找的时候,利用一个set存放当前已有向量,那么下次如果又出现肯定就是不能加入的点,利用set去搞,然后建完