Thrilling Teleporters: Find Minimum Jumps to Traverse a Graph with Teleport Edges

Question

## Problem

You have a graph with `n` nodes. Most edges cost 1 jump. Some edges are "teleporters" that cost 0 jumps (you are instantly transported). Find the minimum number of jumps to travel from node `src` to node `dst`.

```python
def min_jumps(
    n: int,
    edges: list[tuple[int, int, int]],  # (u, v, cost) cost in {0,1}
    src: int,
    dst: int
) -> int:  # -1 if unreachable
    pass
```

**Example:**
```
n = 5
edges = [(0,1,1),(1,2,0),(2,3,1),(0,3,1),(3,4,0)]
src = 0, dst = 4

Path 0->1->2->3->4: costs 1+0+1+0 = 2 jumps
Path 0->3->4:        costs 1+0   = 1 jump
Output: 1
```

## Approach

Use 0-1 BFS (deque): enqueue with `appendleft` for 0-cost edges and `append` for 1-cost edges. This gives correct shortest paths without a full Dijkstra.

## Follow-ups

1. Why does 0-1 BFS produce correct shortest paths? Prove the invariant.
2. How does 0-1 BFS compare to Dijkstra in time complexity for this problem?
3. What if teleporters are one-directional (directed graph)? Does your algorithm change?
4. What if there are also "super teleporters" that take you back 1 jump (negative cost)? What algorithm handles this?

Thrilling Teleporters: Find Minimum Jumps to Traverse a Graph with Teleport Edges

Question Details

Full Details

Topics

More from Karat