题并不难, 简单的 BFS 就可以解决, 但是需要一个二维的 dis 数组, 保存两种不同的状态, 到此节点的路线是蓝色的还是红色的两种.
比赛的时候没做出来, 图相关的题做得少, 看到就犯怵, 以后还是要多写一点图的算法.
const shortestAlternatingPaths = function (n, red_edges, blue_edges) {
const g = new Array(n);
for (let i = 0; i < n; ++i) g[i] = [];
const q = [];
const dis = [[], []];
const visit = [];
for (let i = 0; i < n; i++) {
dis[0][i] = Number.MAX_SAFE_INTEGER;
dis[1][i] = Number.MAX_SAFE_INTEGER;
visit[i] = false;
for (let j = 0; j < n; j++) g[i][j] = 'n';
}
for (let i = 0; i < red_edges.length; i++) {
const [a, b] = red_edges[i];
g[a][b] = 'r';
}
for (let i = 0; i < blue_edges.length; i++) {
const [a, b] = blue_edges[i];
if (g[a][b] === 'r') g[a][b] = 'a';
else g[a][b] = 'b';
}
q.push({ node: 0, val: 0 });
dis[0][0] = 0; // 到第 n 个节点的最短距离, 且最后到达此节点的边是蓝色
dis[1][0] = 0;
// 若 val 为正数, 表明到达此节点的边为蓝色
while (q.length > 0) {
const t = q.shift();
for (let i = 0; i < g[t.node].length; i++) {
const n = g[t.node][i];
if (n === "b" || n === 'a') {
if (t.val <= 0 && dis[0][i] > dis[1][t.node] + 1) {
dis[0][i] = dis[1][t.node] + 1;
q.push({ node: i, val: -t.val + 1 })
}
}
if (n === 'r' || n === 'a') {
if (t.val >= 0 && dis[1][i] > dis[0][t.node] + 1) {
dis[1][i] = dis[0][t.node] + 1;
q.push({ node: i, val: -t.val - 1 });
}
}
}
}
const r = [];
for (let i = 0; i < dis[0].length; i++) {
r[i] = Math.min(dis[0][i], dis[1][i]);
if (r[i] === Number.MAX_SAFE_INTEGER)
r[i] = -1;
}
return r;
};