class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
}
};
1129. 颜色交替的最短路径
在一个有向图中，节点分别标记为 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。
示例 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]
示例 3：
输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]] 输出：[0,-1,-1]
示例 4：
输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]] 输出：[0,1,2]
示例 5：
输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]] 输出：[0,1,1]
提示：
1 <= n <= 100red_edges.length <= 400blue_edges.length <= 400red_edges[i].length == blue_edges[i].length == 20 <= red_edges[i][j], blue_edges[i][j] < n原站题解
java 解法, 执行用时: 3 ms, 内存消耗: 41.8 MB, 提交时间: 2023-02-02 09:42:39
class Solution {
public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
List<Integer>[][] next = new List[2][n];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) {
next[i][j] = new ArrayList<Integer>();
}
}
for (int[] edge : redEdges) {
next[0][edge[0]].add(edge[1]);
}
for (int[] edge : blueEdges) {
next[1][edge[0]].add(edge[1]);
}
int[][] dist = new int[2][n]; // 两种类型的颜色最短路径的长度
for (int i = 0; i < 2; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
}
Queue<int[]> queue = new ArrayDeque<int[]>();
dist[0][0] = 0;
dist[1][0] = 0;
queue.offer(new int[]{0, 0});
queue.offer(new int[]{0, 1});
while (!queue.isEmpty()) {
int[] pair = queue.poll();
int x = pair[0], t = pair[1];
for (int y : next[1 - t][x]) {
if (dist[1 - t][y] != Integer.MAX_VALUE) {
continue;
}
dist[1 - t][y] = dist[t][x] + 1;
queue.offer(new int[]{y, 1 - t});
}
}
int[] answer = new int[n];
for (int i = 0; i < n; i++) {
answer[i] = Math.min(dist[0][i], dist[1][i]);
if (answer[i] == Integer.MAX_VALUE) {
answer[i] = -1;
}
}
return answer;
}
}
javascript 解法, 执行用时: 104 ms, 内存消耗: 50.5 MB, 提交时间: 2023-02-02 09:42:20
/**
* @param {number} n
* @param {number[][]} redEdges
* @param {number[][]} blueEdges
* @return {number[]}
*/
var shortestAlternatingPaths = function(n, redEdges, blueEdges) {
const next = new Array(2).fill(0).map(() => new Array(n).fill(0).map(() => new Array()));
for (const edge of redEdges) {
next[0][edge[0]].push(edge[1]);
}
for (const edge of blueEdges) {
next[1][edge[0]].push(edge[1]);
}
const dist = new Array(2).fill(0).map(() => new Array(n).fill(Number.MAX_VALUE)); // 两种类型的颜色最短路径的长度
const queue = [];
dist[0][0] = 0;
dist[1][0] = 0;
queue.push([0, 0]);
queue.push([0, 1]);
while (queue.length) {
const pair = queue.shift();
let x = pair[0], t = pair[1];
for (const y of next[1 - t][x]) {
if (dist[1 - t][y] !== Number.MAX_VALUE) {
continue;
}
dist[1 - t][y] = dist[t][x] + 1;
queue.push([y, 1 - t]);
}
}
const answer = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
answer[i] = Math.min(dist[0][i], dist[1][i]);
if (answer[i] === Number.MAX_VALUE) {
answer[i] = -1;
}
}
return answer;
};
golang 解法, 执行用时: 8 ms, 内存消耗: 5.2 MB, 提交时间: 2023-02-02 09:42:02
func shortestAlternatingPaths(n int, redEdges, blueEdges [][]int) []int {
type pair struct{ x, color int }
g := make([][]pair, n)
for _, e := range redEdges {
g[e[0]] = append(g[e[0]], pair{e[1], 0})
}
for _, e := range blueEdges {
g[e[0]] = append(g[e[0]], pair{e[1], 1})
}
dis := make([]int, n)
for i := range dis {
dis[i] = -1
}
vis := make([][2]bool, n)
vis[0] = [2]bool{true, true}
q := []pair{{0, 0}, {0, 1}}
for level := 0; len(q) > 0; level++ {
tmp := q
q = nil
for _, p := range tmp {
x := p.x
if dis[x] < 0 {
dis[x] = level
}
for _, to := range g[x] {
if to.color != p.color && !vis[to.x][to.color] {
vis[to.x][to.color] = true
q = append(q, to)
}
}
}
}
return dis
}
python3 解法, 执行用时: 40 ms, 内存消耗: 15.1 MB, 提交时间: 2023-02-02 09:41:40
'''
BFS, 0=红，1=蓝，
'''
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))
dis = [-1] * n
vis = {(0, 0), (0, 1)}
q = [(0, 0), (0, 1)]
level = 0
while q:
tmp = q
q = []
for x, color in tmp:
if dis[x] == -1:
dis[x] = level
for p in g[x]:
if p[1] != color and p not in vis:
vis.add(p)
q.append(p)
level += 1
return dis
python3 解法, 执行用时: 48 ms, 内存消耗: 15.2 MB, 提交时间: 2022-08-01 11:09:00
class Solution:
def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
'''
BFS，从节点0起，每次take one step，这样保证到达每个节点时路径是最短的。
而我们并不知道节点0到达节点i的最短路径，是'红蓝红...'还是'蓝红蓝...'，
所以我们需要都找出来，用nx2的数组dist保存，最后再选短的那个。
'''
red_path = [set() for i in range(n)]
blue_path = [set() for i in range(n)]
dist = [[None, None] for i in range(n)]
dist[0] = [0, 0]
step = 0
now_red = [0]
now_blue = [0]
for start, end in red_edges:
red_path[start].add(end)
for start, end in blue_edges:
blue_path[start].add(end)
# step 1 找到分别以红边开始和以蓝边开始的两条最短路径
while len(now_red) != 0 or len(now_blue) != 0 :
new_red, new_blue = [], []
step += 1
if len(now_blue) != 0:
for point in now_blue:
for next_point in red_path[point]:
if dist[next_point][0] is None:
new_red.append(next_point)
dist[next_point][0] = step
if len(now_red) != 0:
for point in now_red:
for next_point in blue_path[point]:
if dist[next_point][1] is None:
new_blue.append(next_point)
dist[next_point][1] = step
now_red, now_blue = new_red, new_blue
# step 2 在这两条最短路径中选择小的，merge成我们的答案
ans = []
for i in range(n):
if dist[i][0] is None and dist[i][1] is None:
ans.append(-1)
elif dist[i][0] is not None and dist[i][1] is not None:
ans.append(min(dist[i][0], dist[i][1]))
elif dist[i][0] is not None:
ans.append(dist[i][0])
else:
ans.append(dist[i][1])
return ans