题并不难, 简单的 BFS 就可以解决, 但是需要一个二维的 dis 数组, 保存两种不同的状态, 到此节点的路线是蓝色的还是红色的两种.

比赛的时候没做出来, 图相关的题做得少, 看到就犯怵, 以后还是要多写一点图的算法.

const shortestAlternatingPaths = function (n, red_edges, blue_edges) {
  const g = new Array(n);
  for (let i = 0; i < n; ++i) g[i] = [];
  const q = [];
  const dis = [[], []];
  const visit = [];
  for (let i = 0; i < n; i++) {
    dis[0][i] = Number.MAX_SAFE_INTEGER;
    dis[1][i] = Number.MAX_SAFE_INTEGER;
    visit[i] = false;
    for (let j = 0; j < n; j++) g[i][j] = 'n';
  }
  for (let i = 0; i < red_edges.length; i++) {
    const [a, b] = red_edges[i];
    g[a][b] = 'r';
  }
  for (let i = 0; i < blue_edges.length; i++) {
    const [a, b] = blue_edges[i];
    if (g[a][b] === 'r') g[a][b] = 'a';
    else g[a][b] = 'b';
  }
  q.push({ node: 0, val: 0 });
  dis[0][0] = 0; // 到第 n 个节点的最短距离, 且最后到达此节点的边是蓝色
  dis[1][0] = 0;
  // 若 val 为正数, 表明到达此节点的边为蓝色
  while (q.length > 0) {
    const t = q.shift();
    for (let i = 0; i < g[t.node].length; i++) {
      const n = g[t.node][i];
      if (n === "b" || n === 'a') {
        if (t.val <= 0 && dis[0][i] > dis[1][t.node] + 1) {
          dis[0][i] = dis[1][t.node] + 1;
          q.push({ node: i, val: -t.val + 1 })
        }
      }
      if (n === 'r' || n === 'a') {
        if (t.val >= 0 && dis[1][i] > dis[0][t.node] + 1) {
          dis[1][i] = dis[0][t.node] + 1;
          q.push({ node: i, val: -t.val - 1 });
        }
      }
    }
  }
  const r = [];
  for (let i = 0; i < dis[0].length; i++) {
    r[i] = Math.min(dis[0][i], dis[1][i]);
    if (r[i] === Number.MAX_SAFE_INTEGER)
      r[i] = -1;
  }
  return r;
};