【图论】B_1129. 颜色交替的最短路径（bfs / dfs）
一、题目描述
A1：题中并没有明确指定节点 0 是红色或者蓝色。
作者：wnjkhd
Consider a directed graph, with nodes labelled 0, 1, …, n-1. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.
Each [i, j] in red_edges denotes a red directed edge from node i to node j. Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.
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 doesn’t exist).
Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]
二、题解
方法一：bfs
为了解决重边与自环，我们约定，这样就不会被遍历多次了：
vis[u][v][0]：表示从结点 u 到 v 且颜色为蓝色的结点已访问。
vis[u][v][1]：表示从结点 u 到 v 且颜色为红色的结点已访问。
在结点中加入颜色的标记，下一次往颜色不同于当前颜色的结点遍历。
其实也可以把蓝图和红图个抽象为边权为 1 的图，为两个图都设定一个标记 boolean[] vis1，boolean[] vis2。
Q&A：
Q1：一开始为什么要将两个颜色的结点入队呢？不是应该是只讲红结点入队吗，因为只有在红图有起点。A1：题中并没有明确指定节点 0 是红色或者蓝色。
int MAXN = 400 + 50;
Edge[] e1, e2;
int[] h1, h2, res;
int tot1, tot2;
final int BLUE = 0, RED = 1, INF = 0x3f3f3f3f;
void addEdge1(int u, int v) {
e1[++tot1] = new Edge();
e1[tot1].to = v;
e1[tot1].next = h1[u];
h1[u] = tot1;
}
void addEdge2(int u, int v) {
e2[++tot2] = new Edge();
e2[tot2].to = v;
e2[tot2].next = h2[u];
h2[u] = tot2;
}
void dijkstra(int s) {
Queue q = new ArrayDeque();
q.add(new Node(s, RED));
q.add(new Node(s, BLUE));
int depth = 0;
boolean[][][] vis = new boolean[MAXN][MAXN][2];
for (int i = 0; i 0) {
Node t = q.poll();
if (t.c == RED) {
for (int i = h2[t.id]; i != 0; i = e2[i].next) {
int to = e2[i].to;
if (!vis[t.id][to][BLUE]) {
res[to] = Math.min(res[to], depth);
q.add(new Node(to, BLUE));
vis[t.id][to][BLUE] = true;
}
}
}else if (t.c == BLUE) {
for (int i = h1[t.id]; i != 0; i = e1[i].next) {
int to = e1[i].to;
if (!vis[t.id][to][RED]) {
res[to] = Math.min(res[to], depth);
q.add(new Node(to, RED));
vis[t.id][to][RED] = true;
}
}
}
}
}
}
public int[] shortestAlternatingPaths(int n, int[][] re, int[][] bu) {
e1 = new Edge[MAXN];e2 = new Edge[MAXN];
h1 = new int[MAXN];h2 = new int[MAXN];
for (int[] r : re) {
addEdge1(r[0], r[1]);
}for (int[] b : bu) {
addEdge2(b[0], b[1]);
}
res = new int[n];
dijkstra(0);
res[0] = 0;
for (int i = 1; i < n; i++) {
if (res[i] == INF)
res[i] = -1;
}
return res;
}
class Node {
int id, c;
Node(int id, int c) {
this.id = id;
this.c = c;
}
}
class Edge {
int to, next;
Edge() {}
}
复杂度分析
时间复杂度：O(M+N)O(M+N)O(M+N)，
空间复杂度：O(...)O(...)O(...)，
方法二：dfs
复杂度分析
时间复杂度：O()O()O()，
空间复杂度：O()O()O()，
作者：wnjkhd
