1129. Shortest Path with Alternating Colors

1129. Shortest Path with Alternating Colors

Medium

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).

Example 1:

Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]

Example 3:

Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]

Example 4:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]

Example 5:

Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]

Constraints:

• 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

思路

map[color][i][j] 记录用 color 颜色的边从 i 到 j 的可达性。（color 0 表示 红，1 表示 蓝）

visited[color][i] 记录从 color 颜色的边到达 i 的最短距离。

先考虑从 0 用红色的边出发：

那么设置 color_state 为 0。初始化 to_depart 数组为 [0]，初始化 round 为 1。开始循环：

• 当 to_depart 不为空时，对其中每一个点 node：
  • 检查 0 – n 的所有点，判断是否可以用 color 颜色的边从 node 到达 i。
    • 若是，则更新 visited[color_state][i] = round ，并将 i 填入 to_depart_buf。
• 交换 to_depart 和 to_depart_buf。
• 更新 color_state 为另一个颜色。
• round++

遍历 i 从 0 到 n，根据两种 color_state 的 visited[color_state][i] ，将其中较小的非 -1 的值记录，得到 distance_start_with_red。

类似地，考虑从 0 用蓝色的边出发，得到 distance_start_with_blue。

最后取 distance_start_with_red 和 distance_start_with_blue 每个 index 处较小的非 -1 的值，即为最终结果。

int get_path(int a, int b) {
    if (a != -1) {
        if (b != -1) {
            return a < b ? a : b;
        } else {
            return a;
        }
    } else {
        return b;
    }
}

vector<int> calculate_distance(int n, bool ***map, int color_state) {
    // color_state 0: to use red. 1: to use blue.
    vector<int> *to_depart = new vector<int>;
    to_depart->emplace_back(0);
    vector<int> *to_depart_buf = new vector<int>;
    int **visited = new int*[2];
    for (int i = 0; i < 2; ++i) {
        visited[i] = new int[n];
        visited[i][0] = 0;
        for (int j = 1; j < n; ++j) {
            visited[i][j] = -1;
        }
    }

    bool first_round = true;
    int round = 1;
    while (!to_depart->empty()) {
        for (auto node: (*to_depart)) {
            for (int i = 0; i < n; ++i) {
                if (map[color_state][node][i]) {  // can go from node to i
                    if (visited[color_state][i] < 0) {
                        visited[color_state][i] = round;
                        to_depart_buf->emplace_back(i);
                    }
                }
            }
        }
        
        vector<int> *tmp;
        tmp = to_depart;
        to_depart = to_depart_buf;
        to_depart_buf = tmp;
        to_depart_buf->clear();
        color_state = (color_state + 1) % 2;
        round++;
    }
    
    vector<int> result;
    for (int i = 0; i < n; ++i) {
        result.emplace_back(get_path(visited[0][i], visited[1][i]));
    }

    for (int i = 0; i < 2; ++i) {
        delete [] visited[i];
    }
    delete [] visited;
    delete to_depart;
    delete to_depart_buf;
    
    return result;
}

class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
        bool ***map = new bool**[2];
        for (int i = 0; i < 2; ++i) {
            map[i] = new bool*[n];
            for (int j = 0; j < n; ++j) {
                map[i][j] = new bool[n];
                for (int k = 0; k < n; ++k) {
                    map[i][j][k] = false;
                }
            }
        }
        
        // map[0][i][j] means there is a red edge from i to j
        // map[1][i][j] means there is a blue edge from i to j
        for (auto red_edge: red_edges) {
            map[0][red_edge[0]][red_edge[1]] = true;
        }
        for (auto blue_edge: blue_edges) {
            map[1][blue_edge[0]][blue_edge[1]] = true;
        }
        
        vector<int> distance_start_with_red = calculate_distance(n, map, 0);
        vector<int> distance_start_with_blue = calculate_distance(n, map, 1);
        
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < n; ++j) {
                delete [] map[i][j];
            }
            delete [] map[i];
        }
        delete [] map;
        
        vector<int> result;
        for (int i = 0; i < n; ++i) {
            result.emplace_back(get_path(distance_start_with_red[i], distance_start_with_blue[i]));
        }
           
        return result;
    }
};

Runtime: 16 ms, faster than 86.55% of C++ online submissions for Shortest Path with Alternating Colors.

Memory Usage: 16.2 MB, less than 18.97% of C++ online submissions for Shortest Path with Alternating Colors.