-
Notifications
You must be signed in to change notification settings - Fork 0
/
1129--shortest-path-with-alternating-colors.js
74 lines (62 loc) · 2.49 KB
/
1129--shortest-path-with-alternating-colors.js
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 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 node ai to node bi in the graph, and
// blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj in 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.
// --- Examples
// Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
// Output: [0,1,-1]
// Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
// Output: [0,1,-1]
// --- Constraints
// 1 <= n <= 100
// 0 <= redEdges.length, blueEdges.length <= 400
// redEdges[i].length == blueEdges[j].length == 2
// 0 <= ai, bi, uj, vj < n
const getNodeInfo = (node, color) => `${node}-${color}`;
const RED = 0;
const BLUE = 1;
/**
* @param {number} n
* @param {number[][]} redEdges
* @param {number[][]} blueEdges
* @return {number[]}
*/
var shortestAlternatingPaths = function (n, redEdges, blueEdges) {
const edgesByColor = [redEdges, blueEdges];
const destNodesByColor = [new Map(), new Map()];
const distances = Array(n).fill(-1);
for (let node = 0; node < n; node++) {
destNodesByColor[RED][node] = [];
destNodesByColor[BLUE][node] = [];
}
for (const [color, edges] of edgesByColor.entries()) {
for (const [srcNode, destNode] of edges) {
destNodesByColor[color][srcNode].push(destNode);
}
}
const queue = [[0, 0, null]]; // source node, source distance, source edge color
const visited = new Set([getNodeInfo(0, null)]);
while (queue.length > 0) {
const [srcNode, srcDistance, srcColor] = queue.shift();
if (distances[srcNode] === -1) {
distances[srcNode] = srcDistance;
} else {
distances[srcNode] = Math.min(distances[srcNode], srcDistance);
}
for (const [destColor, destNodes] of destNodesByColor.entries()) {
if (srcColor !== destColor) {
for (const destNode of destNodes[srcNode]) {
const destInfo = getNodeInfo(destNode, destColor);
if (!visited.has(destInfo)) {
visited.add(destInfo);
queue.push([destNode, srcDistance + 1, destColor]);
}
}
}
}
}
return distances;
};