跳到主要内容

1129.颜色交替的最短路径

· 阅读需 3 分钟

1、题干​

给定一个整数 n，即有向图中的节点数，其中节点标记为 0 到 n - 1。图中的每条边为红色或者蓝色，并且可能存在自环或平行边。

给定两个数组 redEdges 和 blueEdges，其中：

  • redEdges[i] = [ai, bi] 表示图中存在一条从节点 ai 到节点 bi 的红色有向边，
  • blueEdges[j] = [uj, vj] 表示图中存在一条从节点 uj 到节点 vj 的蓝色有向边。

返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。

 

示例 1：

输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]

示例 2：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]

 

提示：

  • 1 <= n <= 100
  • 0 <= redEdges.length, blueEdges.length <= 400
  • redEdges[i].length == blueEdges[j].length == 2
  • 0 <= ai, bi, uj, vj < n

2、思路​

整体思路分为 建表 和 BFS 两步：

  • 建表：将所有邻接点关系存入二维矩阵，第一维下标表示出发点，第二维元素表示到达点，到达点使用正负数表示红蓝两种状态
  • BFS：广度优先搜索所有可能存在的红蓝交替路径，找出最短路径

3、代码​

function shortestAlternatingPaths(n: number, redEdges: number[][], blueEdges: number[][]): number[] {
    const edges: Set<number>[] = new Array(n).fill(0).map(() => new Set());
    for (const [e0, e1] of redEdges) edges[e0].add(e1);
    for (const [e0, e1] of blueEdges) edges[e0].add(-e1);

    const ans = new Array(n).fill(Infinity);
    let nodes = edges[0], visited = new Set([0]);

    for (let depth = 1; nodes.size; depth++) {
        const nextNodes: Set<number> = new Set();

        for (const n of nodes) {
            if (visited.has(n)) continue;
            visited.add(n);

            const i = n < 0 ? -n : n;
            ans[i] = Math.min(ans[i], depth);

            for (const e of edges[i]) {
                if (Math.sign(n) !== Math.sign(e)) nextNodes.add(e);
            }
        }

        nodes = nextNodes;
    }

    return ans[0] = 0, ans.map(a => a === Infinity ? -1 : a);
}

4、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

5、执行结果​

image.png