↓Skip to main content
  1. Posts/

LeetCode-1129 颜色交替的最短路径

·1 min·
Table of Contents

LeetCode-1129 颜色交替的最短路径 #

Solution 1 #

BFS 时记录访问某个点时通过的边的颜色即可.

代码如下:

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        g = [[] for _ in range(n)]
        for x, y in redEdges:
            g[x].append((y, 0))
        for x, y in blueEdges:
            g[x].append((y, 1))

        ans = [-1 for _ in range(n)]
        vis = {(0, 0), (0, 1)}
        q = [(0, 0), (0, 1)]
        r = 0
        while q:
            nxt_q = []
            for x, xc in q:
                if ans[x] == -1:
                    ans[x] = r
                for y, yc in g[x]:
                    if (y, yc) not in vis and yc != xc:
                        vis.add((y, yc))
                        nxt_q.append((y, yc))
            r += 1
            q = nxt_q.copy()
        return ans