# 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.

def solution(roads, start, end, k, require_bike_lanes, closed_roads):
    import heapq
    from collections import defaultdict

    if k <= 0:
        return []
    if start == end:
        return [(0, [start])]

    def normalize(a, b):
        return (a, b) if a <= b else (b, a)

    closed = {normalize(u, v) for u, v in closed_roads}
    graph = defaultdict(list)

    for u, v, distance, bike_lane, elevation_gain, traffic_risk in roads:
        if normalize(u, v) in closed:
            continue
        if require_bike_lanes and bike_lane == 0:
            continue

        cost = distance + 2 * elevation_gain + 3 * traffic_risk
        graph[u].append((v, cost))
        graph[v].append((u, cost))

    if start not in graph or end not in graph:
        return []

    for node in graph:
        graph[node].sort(key=lambda item: item[0])

    heap = [(0, (start,), start)]
    routes = []

    while heap and len(routes) < k:
        total_cost, path, node = heapq.heappop(heap)

        if node == end:
            routes.append((total_cost, list(path)))
            continue

        visited = set(path)
        for neighbor, edge_cost in graph[node]:
            if neighbor in visited:
                continue
            heapq.heappush(heap, (total_cost + edge_cost, path + (neighbor,), neighbor))

    return routes