I. Spider Walk

Key Observations

• Instead of thinking about geometric strands, think about the autopilot trajectories of all $n$ starting strands. As radius increases, these trajectories cross whenever an existing bridge swaps two adjacent strands.

• Each trajectory is a polyline from an inner endpoint to an outer endpoint. Moving along a trajectory costs $0$.

• Between two consecutive bridge distances, the order of trajectories is fixed. In that annulus, Charlotte may add a new bridge between any two adjacent geometric strands, which is exactly the same as switching between two adjacent trajectories. Each such switch costs $1$.

• Therefore the whole problem becomes a shortest-path problem in a graph:

  • vertices represent trajectory segments between consecutive crossings,

  • directed edges of cost $0$ connect consecutive segments of the same trajectory from inner to outer radius,

  • bidirectional edges of cost $1$ connect adjacent trajectory segments within one annulus.

  • We never need one vertex per strand per annulus. A new vertex is created only when a trajectory itself crosses a bridge or one of its adjacent trajectories changes, so each bridge causes only $O(1)$ fresh vertices.

  Algorithm

  1. Sort all existing bridges by increasing distance from the center.

  2. Sweep outward and maintain:

     • order[pos]: which starting trajectory currently occupies geometric position pos,

     • active[label]: the current graph vertex for the still-open segment of that trajectory.

     • Initially, each starting strand contributes one graph vertex. Since all trajectories are adjacent in the initial annulus, add cost-$1$ edges between consecutive positions on the cycle.

     • When processing a bridge on strands $t$ and $t+1$ (cyclically):

       • first swap the two trajectories in order, because this describes the new annulus just outside the bridge;

       • the only trajectories whose set of adjacent trajectories may have changed are those currently occupying positions \[ \text{prev}(t),\ t,\ t+1,\ \text{next}(t+1). \] For each distinct such position, create a new graph vertex for the trajectory now occupying it and connect its previous vertex to this new vertex by a directed cost-$0$ edge;

       • in the new annulus, every adjacency involving one of these refreshed positions starts a new interval, so add cost-$1$ edges for all cyclic adjacent pairs touching them.

       • After the sweep, the trajectory currently occupying outer strand $s$ is the target. Run $0$-$1$ BFS on the reversed graph from its final graph vertex.

       • The answer for starting strand $i$ is the distance from this target to the initial graph vertex of trajectory $i$. enumerate

         Correctness Proof

         We prove that the algorithm returns the correct answer.

         Lemma 1.

         Every valid movement of Charlotte corresponds to a path in the constructed graph with the same cost.

         Proof.

         Whenever Charlotte follows the web without adding a bridge, she stays on one autopilot trajectory. In the graph this is exactly moving along cost-$0$ edges between consecutive segments of that trajectory.

         If Charlotte adds a bridge in some annulus, she switches between two adjacent geometric strands. Since the order of trajectories in that annulus is fixed, this is precisely a switch between two adjacent trajectory segments, represented by one cost-$1$ edge.

         Thus every physical walk maps to a graph path whose total cost equals the number of added bridges. □

         Lemma 2.

         Every path in the constructed graph corresponds to a valid strategy for Charlotte with the same cost.

         Proof.

         Cost-$0$ edges connect consecutive pieces of the same trajectory across a crossing, so traversing them means simply continuing outward and taking the required existing bridge.

         Cost-$1$ edges connect two adjacent trajectory segments that coexist in one annulus. Charlotte can place a new bridge anywhere inside that annulus and switch exactly once between those two trajectories. Therefore every graph path can be realized physically, with one added bridge for each cost-$1$ edge. □

         Lemma 3.

         The graph has exactly the transitions needed to describe all possible strategies.

         Proof.

         Initially each trajectory has one segment. Every existing bridge splits exactly the two trajectories that cross there, and may also change the local neighbors of the two immediately adjacent trajectories. Hence after one bridge, only the four cyclic positions \[ \text{prev}(t),\ t,\ t+1,\ \text{next}(t+1) \] need fresh segment vertices. So the sweep creates only $O(1)$ new vertices per bridge.

         Within a fixed annulus, only adjacent trajectories can be connected by a newly added bridge, so the graph contains exactly those cost-$1$ edges. A bridge crossing changes only local adjacency, hence only a constant number of adjacency pairs need to be updated after each event. No other transitions are created or lost. □

         Theorem.

         The algorithm outputs the correct answer for every valid input.

         Proof.

         By Lemmas 1 and 2, minimum added bridges from a starting strand to outer strand $s$ are exactly equal to shortest-path distance in the directed constructed graph from the initial segment of that trajectory to the final segment that exits at strand $s$. By Lemma 3, the graph contains all and only valid transitions. Running $0$-$1$ BFS on the reversed graph from the target computes these same shortest-path distances to all starting vertices at once. Therefore each printed distance is correct. □

         Complexity Analysis

         Sorting the bridges takes $O(m \log m)$ time.

         The graph has $O(n+m)$ vertices and edges:

         • $O(n+4m)$ trajectory-segment vertices,

         • $O(n+m)$ zero-cost and unit-cost edges.

         • The sweep is linear after sorting, and $0$-$1$ BFS is also linear in the graph size. Therefore the total time complexity is \[ O(m \log m + n + m), \] and memory usage is \[ O(n+m). \]

         Implementation Notes

         • Strand $n$ is adjacent to strand $1$, so all position updates are cyclic.

         • Multiple cost-$1$ edges between the same pair of vertices are harmless; $0$-$1$ BFS handles them naturally.

         • The target is the trajectory that ends at strand $s$, not necessarily the trajectory that started at strand $s$.