Medium · Graphs

BFS Shortest Reach

Given n nodes numbered 1..n, undirected edges [u, v] and a start node, return the shortest distance from start to every other node in node order — each edge counts 6, −1 if unreachable — leaving start itself out (all −1 if start is not in 1..n). The examples show the graph as 0-indexed adjacency lists with a 0-indexed start; the judge passes n = len(adj), 1-indexed edge pairs and start + 1.

Examples

Example 1

{
  "adj": [
    [1, 2],
    [0, 3],
    [0, 3],
    [1, 2, 4],
    [3],
    []
  ],
  "pos": [
    [176, 44],
    [262, 94],
    [262, 193],
    [176, 242],
    [90, 193],
    [90, 93]
  ],
  "start": 0
}

Output: [6, 6, 12, 18, -1] · 4 reached

Example 2

{
  "adj": [
    [1],
    [0, 2, 3],
    [1, 4],
    [1],
    [2],
    []
  ],
  "pos": [
    [176, 44],
    [262, 94],
    [262, 193],
    [176, 242],
    [90, 193],
    [90, 93]
  ],
  "start": 0
}

Output: [6, 12, 12, 18, -1] · 4 reached

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.