847.访问所有节点的最短路径

链接：847.访问所有节点的最短路径
难度：Hard
标签：位运算、广度优先搜索、图、动态规划、状态压缩
简介：返回能够访问所有节点的最短路径的长度。

题解 1 - typescript

• 编辑时间：2021-08-06
• 执行用时：120ms
• 内存消耗：45MB
• 编程语言：typescript
• 解法介绍：bfs,利用 set 做重复值过滤。

function shortestPathLength(graph: number[][]): number {
  const n = graph.length;
  const queue: [number, number, number][] = [];
  const seen = new Array(n).fill(0).map(_ => new Set<number>());
  for (let i = 0; i < n; i++) {
    queue.push([i, 1 << i, 0]);
    seen[i].add(1 << i);
  }
  let ans = Infinity;
  while (queue.length) {
    const data = queue.shift()!;
    const [idx, mask, step] = data;
    if (mask === (1 << n) - 1) {
      ans = step;
      break;
    }
    for (const next of graph[idx]) {
      const newMask = mask | (1 << next);
      if (seen[next].has(newMask)) continue;
      queue.push([next, newMask, step + 1]);
      seen[next].add(newMask);
    }
  }
  return ans;
}