题解

问题分析

• 城市按顺时针排列在凸多边形边界上
• 某些道路被巡逻，不能直接走，但可以在路口（道路交点）穿越
• 只能在路口处转向
• 求从城市 $n$ 到城市 $1$ 的最短安全路径

关键观察

1. 凸多边形性质：所有对角线都在多边形内部相交
2. 路径结构：路径由若干直线段组成，只能在路口转向
3. 建模思路：将问题转化为图论最短路问题

解法思路

1. 图模型构建

• 顶点：所有城市 + 所有被巡逻道路的交点
• 边：连接相邻顶点之间的直线段
  • 同一道路上的相邻交点
  • 相邻城市之间的边界段

2. 几何处理

• 计算所有被巡逻道路之间的交点
• 对每条道路，将其交点按顺序排列
• 计算相邻顶点之间的欧几里得距离

3. 最短路计算

• 从城市 $n$ 出发，使用 Dijkstra 算法
• 目标点为城市 $1$
• 考虑所有安全路径（不被巡逻的道路段）

算法步骤

1. 读入城市坐标和被巡逻道路
2. 计算所有被巡逻道路之间的交点
3. 为每条道路建立交点序列
4. 构建图：顶点为城市和交点，边为安全路径段
5. 运行 Dijkstra 算法求 $n$ 到 $1$ 的最短路
6. 输出路径长度

复杂度分析

• 交点总数：$O(m^2)$，但实际中可通过几何性质优化
• 最短路：$O((V+E)\log V)$，其中 $V$ 为顶点数，$E$ 为边数

优化考虑

• 利用凸多边形性质减少不必要的交点计算
• 只考虑可能出现在最短路径上的道路和交点
• 预处理相邻城市间的边界距离

样例解释

样例中路径：$6 \rightarrow 4 \rightarrow (2-5\ 道路交点) \rightarrow 1$

• 总长度 $42$：由若干直线段距离求和得到
• 避开了所有被巡逻道路的直接通行，只在路口穿越