1129. 颜色交替的最短路径

Posted on | In | |

在一个有向图中，节点分别标记为 0, 1, …, n-1。图中每条边为红色或者蓝色，且存在自环或平行边。
red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地，blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。
返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shortest-path-with-alternating-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算是接触的第一到图题，很多相关概念都忘记了，题干也没太看懂，重新整理了一下图的相关概念后，在评论区找了一段代码，题的思路和广度优先遍历弄明白了一些，但是也没完全弄懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def shortestAlternatingPaths(self, n, redEdges, blueEdges):
        """
        :type n: int
        :type redEdges: List[List[int]]
        :type blueEdges: List[List[int]]
        :rtype: List[int]
        """
        g = defaultdict(list)
        for a, b in redEdges:
            g[a].append(-b)
        for a, b in blueEdges:
            g[-a].append(b)
        print(g)
        ret = [-1] * n
        vis = set()
        q = deque([0])
        vis.add(0)
        s = 0
        while q:
            for _ in range(len(q)):
                p = q.pop()
                if ret[abs(p)] == -1:
                    ret[abs(p)] = s
                for x in g[p]:
                    if x not in vis:
                        q.appendleft(x)
                        vis.add(x)
            s += 1
        return ret