~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Bellman-Ford, Floyd-Warshall, 0-1 BFS
Negative edges, all-pairs, and deque BFS for 0/1 weights.
Notes
- Bellman-Ford: relax every edge V-1 times, O(VE). If a V-th round still relaxes something, there's a negative cycle. Running it for exactly k rounds (copying
disteach round) gives "at most k edges". - Floyd-Warshall: all pairs, O(V^3):
for k: for i: for j: d[i][j] = min(d[i][j], d[i][k] + d[k][j]). k must be the outer loop. - 0-1 BFS: weights of 0 or 1. Use a deque: push to the front for weight 0 and to the back for weight 1.
- Unweighted: plain BFS.
6 problems
Advanced & competitive
More shortest paths Bellman-Ford, Floyd-Warshall, 0-1 BFS.
- Basics: Bellman-Ford with negative edges basics py · c++ · java easy
- Fewest climbs on the hiking trails py · c++ · java easy
- Minimum Cost to Make at Least One Valid Path in a Grid py · c++ · java medium
- All-pairs shortest routes py · c++ · java easy
- Highest finishing score, or unbounded py · c++ · java medium
- Currency arbitrage with fees Optiver py · c++ · java medium