Problem
You are given nn cities labeled from 0 to n−1.
Some pairs of cities are connected by roads, and some pairs are connected by bridges.
Roads are free to use.
Each bridge crossing costs 1 token, regardless of direction or distance.
You are also given a starting city start, a destination city target, and an integer k representing how many bridge tokens you have.
You can travel:
Along any road edge at zero cost, unlimited times.
Along any bridge edge, but in total you may use at most
kbridges on your entire route.
Return the minimum number of steps (edges traversed, roads or bridges) needed to travel from start to target without using more than k bridges. If it is impossible, return -1.
A “step” is traversing a single edge (road or bridge) from one city to a directly connected city.
Input format
n: integer, number of cities.roads: list of pairs[u, v]meaning there is an undirected road betweenuandv.bridges: list of pairs[u, v]meaning there is an undirected bridge betweenuandv.start: integer in[0, n-1].target: integer in[0, n-1].k: integer, maximum number of bridges you may use.
Assumptions
The graph can be disconnected.
There may be multiple edges between two cities (e.g., both a road and a bridge).
No self-loops are given, but the code shouldn’t rely on that.
1≤n≤10^5, total edges up to 2⋅10^5.
Example
Input:
n = 5roads = [[0,1],[1,2]]bridges = [[0,3],[3,4],[4,2]]start = 0target = 2k = 1
Questions:
What is the minimum number of steps?
Show the actual path and annotate where you spend your one bridge token.
Answer:
Path with roads only:
0 → 1 → 2, 2 steps, 0 bridges.Longer path using bridges:
0 → 3 → 4 → 2, 3 steps, 2 bridges (invalid ifk = 1).
So the correct answer is 2.
How to participate
Post your solution as a comment (or link a gist) by April 2, 2026 at noon Pacific Time
Include:
Your language
Brief explanation of your approach
Stated complexity
What I’ll do
By April 3, I’ll publish a Review & Lessons post with:
Annotated feedback on selected submissions
A clean reference solution
Notes on how an interviewer would evaluate your approach.
If you’re short on time this week, at least sketch your approach in prose—that’s still valuable practice.