题目描述

考虑一个有向图，点被标记为 0, 1, ..., n-1。在这个图中，每条边为红色或蓝色，可能有自环或重边。

red_edges 中的每一个 [i, j] 表示一条从结点 i 到结点 j 的红的有向边。类似地，blue_edges 中的每一个 [i, j] 表示一条从结点 i 到结点 j 的蓝的有向边。

返回一个长度为 n 的数组 answer，answer[X] 是从结点 0 到结点 X 的最短路径，使得路径中边的颜色交替出现（或者 -1 表示这样的路径不存在）。

样例

输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]

输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]

输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
输出：[0,-1,-1]

输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
输出：[0,1,2]

输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
输出：[0,1,1]

限制

• 1 <= n <= 100
• red_edges.length <= 400
• blue_edges.length <= 400
• red_edges[i].length == blue_edges[i].length == 2
• 0 <= red_edges[i][j], blue_edges[i][j] < n

算法

(宽度优先搜索 / BFS) $O(n + m)$

1. 类似于普通的宽度优先搜索，我们仍然从 0 开始扩展结点。我们首先建立邻接表数据结构。
2. 但这道题要求每次走不同颜色的边，所以我们的状态需要扩充一维，即 dis[i][0] 和 dis[i][1] 分别表示到达结点 i 时，上一次走的是红色边和蓝色边。
3. 初始时，dis[i][j] = MAX，但 dis[0][0] = dis[0][1] = 0。
4. 队列里需要记录数对，扩展时，如果边的颜色和当前结点上一次走的颜色不一致，且目标结点及这个颜色的距离比当前结点及颜色的距离大 2 或以上，则更新距离，然后新结点及颜色入队。
5. 最后答案为 answer[i] = min(dis[i][0], dis[i][1])。

时间复杂度

• 每个点和边都最多遍历一次，故时间复杂度为 $O(n + m)$。

空间复杂度

• 需要邻接矩阵的空间，和队列，距离数组等空间，故空间复杂度为 $O(n + m)$。

C++ 代码

class Solution {
public:
    void bfs(
        const vector<vector<pair<int, int>>>& graph,
        vector<vector<int>>& dis
    ) {
        queue<pair<int, int>> q;
        dis[0][0] = dis[0][1] = 0;
        q.push(make_pair(0, 0));
        q.push(make_pair(0, 1));

        while (!q.empty()) {
            auto &sta = q.front();
            int u = sta.first, uc = sta.second;
            q.pop();

            for (auto &e : graph[u]) {
                int v = e.first, vc = e.second;
                if (uc != vc && dis[v][vc] > dis[u][uc] + 1) {
                    dis[v][vc] = dis[u][uc] + 1;
                    q.push(make_pair(v, vc));
                }
            }
        }
    }

    vector<int> shortestAlternatingPaths(
        int n, 
        vector<vector<int>>& red_edges,
        vector<vector<int>>& blue_edges
    ) {
        const int MAX = 1000000000;
        vector<vector<pair<int, int>>> graph(n);
        for (auto &e : red_edges)
            graph[e[0]].emplace_back(make_pair(e[1], 0));

        for (auto &e : blue_edges)
            graph[e[0]].emplace_back(make_pair(e[1], 1));

        vector<vector<int>> dis(n, vector<int>(2, MAX));
        bfs(graph, dis);

        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = min(dis[i][0], dis[i][1]);
            if (ans[i] == MAX)
                ans[i] = -1;
        }

        return ans;
    }
};