1129. Shortest Path with Alternating Colors ⭐
Medium
You are given an integer
n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.You are given two arrays
redEdges and blueEdges where:redEdges[i] = [ai, bi]indicates that there is a directed red edge from nodeaito nodebiin the graph, andblueEdges[j] = [uj, vj]indicates that there is a directed blue edge from nodeujto nodevjin the graph.
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 does not exist.Example 1:
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]
Example 2:
Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]
Constraints:
1 <= n <= 1000 <= redEdges.length, blueEdges.length <= 400redEdges[i].length == blueEdges[j].length == 20 <= ai, bi, uj, vj < n
func shortestAlternatingPaths(n int, red_edges [][]int, blue_edges [][]int) []int {
// red[0] 會紀錄 node0 有通往哪些其他節點的紅邊
// blue[0] 會紀錄 node0 有通往哪些其他節點的藍邊
red := make([][]int, n)
blue := make([][]int, n)
for _, edge := range red_edges {
red[edge[0]] = append(red[edge[0]], edge[1])
}
for _, edge := range blue_edges {
blue[edge[0]] = append(blue[edge[0]], edge[1])
}
// BFS，queue 存放 這一層 level 要訪問的節點
queue := make([][]int, 0)
queue = append(queue, []int{0, -1}) // 從節點0出發，邊用 -1 特別記錄
// res 記錄 0 到每個點的最短路徑，初始化為 -1，不可到達
res := make([]int, n)
for i := 0; i < n; i ++{
res[i] = -1
}
// 記錄是否從紅藍邊通往某一點過
// 例如：已經從紅邊訪問過節點3，那下次要從紅邊訪問節點3，路徑長必定大於之前紀錄的值，可以跳過
visited := make([][]bool, n)
for j := 0; j < n; j ++{
visited[j] = []bool{false, false}
}
// level，也就是目前路境長
level := 0
// 沒有節點需要拜訪才跳出迴圈
for len(queue) != 0 {
next := [][]int{} // 下一層要遞迴的點
for _, n := range queue { //遞迴拜訪這一層的點
label := n[0] // 這個點的label
color := n[1] // 這個點的顏色
if color != -1 {
visited[label][color] = true // 其他點從紅邊或藍邊訪問過這個點了
}
// 第一次到這個點，目前是最短路徑！記錄起來
if res[label] == -1 {
res[label] = level
}
// 目前是藍色(color=0)或是在節點0，把紅色的邊與要去的點加到下一層要訪問的陣列中
if color == 0 || color == -1 {
for _, neighbor := range red[label] {
if !visited[neighbor][1] {
next = append(next, []int{neighbor, 1})
}
}
}
// 目前是紅色(color=1)或是在節點0，把藍色的邊與要去的點加到下一層要訪問的陣列中
if color == 1 || color == -1 {
for _, neighbor := range blue[label] {
if !visited[neighbor][0] {
next = append(next, []int{neighbor, 0})
}
}
}
}
queue = next // 待會要訪問下一層了！
level++ // 層數 == 路徑長 加1
}
return res
}
Last modified 3mo ago