# Plan Bicycle Routes on a City Map Build a bicycle route planner over a city map modeled as an **undirected, weighted graph**, and return the *K* cheapest simple routes between two intersections. Implement: ```python def solution(roads, start, end, k, require_bike_lanes, closed_roads): ``` ## Inputs - **`roads`** — a list of roads. Each road is a 6-element tuple `(u, v, distance, bike_lane, elevation_gain, traffic_risk)`: - `u`, `v` — the two intersection ids the road connects (the road is **undirected**). - `distance` — a positive integer (`1 <= distance <= 1000`). - `elevation_gain`, `traffic_risk` — integers in the range `0..100`. - `bike_lane` — `1` if the road has a bike lane, `0` otherwise. - **`start`**, **`end`** — the source and destination intersection ids. - **`k`** — the maximum number of routes to return. - **`require_bike_lanes`** — a boolean. If `True`, only roads with `bike_lane == 1` may be used. - **`closed_roads`** — a list of `(u, v)` pairs marking roads that are temporarily closed. These pairs are **undirected**: `(u, v)` and `(v, u)` refer to the same road. Re-calling `solution` with a different `closed_roads` models dynamic map updates. ## Composite cost The bicycle cost of a single road is: ``` cost = distance + 2 * elevation_gain + 3 * traffic_risk ``` The **total cost** of a route is the sum of the costs of the roads along it. ## What to do 1. **Filter the graph.** Drop every road that appears in `closed_roads`. Then, if `require_bike_lanes` is `True`, also drop every road with `bike_lane == 0`. Build the undirected graph from the remaining roads. 2. **Find routes.** Search for **simple** routes from `start` to `end` (a simple route visits each intersection at most once — no repeated intersections). 3. **Rank and trim.** Sort the routes by **total cost ascending**. On a tie, the route whose intersection list is **lexicographically smaller** comes first. Return the first `k` routes. If fewer than `k` feasible routes exist, return all of them. ## Output format Return a list of routes, where **each route is a pair `(total_cost, path)`**: - `total_cost` — the route's total composite cost (an integer). - `path` — the list of intersection ids visited in order, starting with `start` and ending with `end`. The returned list is already sorted by the ranking rule above. ## Edge cases - **`start == end`:** return `[(0, [start])]` immediately (a single zero-cost route consisting of just that intersection), regardless of the roads given — even when `roads` is empty. - **No route exists** (e.g. `start` or `end` has no usable roads after filtering, or `start` and `end` are disconnected once closed / non-bike-lane roads are removed): return `[]`. ## Notes - Roads are undirected, and there is at most one road between any pair of intersections. - Use an **exact** shortest-path / K-shortest-paths search. No coordinate or distance heuristic is provided, so A\*-style estimation is not applicable here.