1129. Shortest Path with Alternating Colors

Consider a directed graph, with nodes labelled 0, 1, ..., n-1.  In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.

Each [i, j] in red_edges denotes a red directed edge from node i to node j.  Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.

Return an array answer of length n, where each answer[X] is the length of the shortest path from node 0 to node X such that the edge colors alternate along the path (or -1 if such a path doesn’t exist).

Example 1:

Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]

Example 3:

Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]

Example 4:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]

Example 5:

Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]

Constraints:

  • 1 <= n <= 100
  • red_edges.length <= 400
  • blue_edges.length <= 400
  • red_edges[i].length == blue_edges[i].length == 2
  • 0 <= red_edges[i][j], blue_edges[i][j] < n

这道题给了一个有向图,跟以往不同的是,这里的边分为两种不同颜色,红和蓝,现在让求从结点0到所有其他结点的最短距离,并且要求路径必须是红蓝交替,即不能有相同颜色的两条边相连。这种遍历图求最短路径的题目的首选解法应该是广度优先遍历 Breadth-first Search,就像迷宫遍历的问题一样,由于其遍历的机制,当其第一次到达某个结点时,当前的步数一定是最少的。不过这道题还有一个难点,就是如何保证路径是红蓝交替的,这就跟以往有些不同了,必须要建立两个图的结构,分别保存红边和蓝边,为了方便起见,使用一个二维数组,最外层用0表示红边,1表示蓝边。内层是一个大小为n的数组,因为有n个结点,数组中的元素是一个 HashSet,因为每个结点可能可以连到多个其他的结点,这个图的结构可以说是相当的复杂了。接下来就是给图结构赋值了,分别遍历红边和蓝边的数组,将对应的结点连上,就是将相连的结点加到 HashSet 中。由于到达每个结点可能通过红边或者蓝边,所以就有两个状态,这里用一个二维的 dp 数组来记录这些状态,其中 dp[i][j] 表示最后由颜色i的边到达结点j的最小距离,除了结点0之外,均初始化为 2n,因为即便是有向图,到达某个结点的最小距离也不可能大于 2n。由于是 BFS 遍历,需要用到 queue,这里的 queue 中的元素需要包含两个信息,当前的结点值,到达该点的边的颜色,所以初始化时分别将 (0,0) 和 (0,1) 放进去,前一个0表示结点值,后一个表示到达该点的边的颜色。接下来就可以进行 BFS 遍历了,进行 while 循环,将队首元素取出,将结点值 cur 和颜色值 color 取出。由于到达当前结点的边的颜色是 color,接下来就只能选另一种颜色了,则可以用 1-color 来选另一种颜色,并且在该颜色下遍历和 cur 相连的所有结点,若其对应的 dp 值仍为 2n,说明是第一次到达该结点,可用当前 dp 值加1来更新其 dp 值,并且将新的结点值与其颜色加入到队列中以便下次遍历其相连结点。当循环结束之后,只需要遍历一次 dp 值,将每个结点值对应的两个 dp 值中的较小的那个放到结果 res 中即可,注意要进行一下判断,若 dp 值仍为 2n,说明无法到达该结点,需要换成 -1,参见代码如下:

class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
        vector<int> res(n);
        vector<vector<int>> dp(2, vector<int>(n));
        vector<vector<unordered_set<int>>> graph(2, vector<unordered_set<int>>(n));
        for (auto &edge : red_edges) {
            graph[0][edge[0]].insert(edge[1]);
        }
        for (auto &edge : blue_edges) {
            graph[1][edge[0]].insert(edge[1]);
        }
        for (int i = 1; i < n; ++i) {
            dp[0][i] = 2 * n;
            dp[1][i] = 2 * n;
        }
        queue<vector<int>> q;
        q.push({0, 0});
        q.push({0, 1});
        while (!q.empty()) {
            int cur = q.front()[0], color = q.front()[1]; q.pop();
            for (int next : graph[1 - color][cur]) {
                if (dp[1 - color][next] == 2 * n) {
                    dp[1 - color][next] = 1 + dp[color][cur];
                    q.push({next, 1 - color});
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            int val = min(dp[0][i], dp[1][i]);
            res[i] = val == 2 * n ? -1 : val;
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1129

参考资料:

https://leetcode.com/problems/shortest-path-with-alternating-colors/

https://leetcode.com/problems/shortest-path-with-alternating-colors/discuss/339964/JavaPython-BFS

https://leetcode.com/problems/shortest-path-with-alternating-colors/discuss/340258/Java-BFS-Solution-with-Video-Explanation

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation