1129. Shortest Path with Alternating Colors

Todo -

• Add Notes
• Add Code
• Add Diagram
• Explain Thought Process
• Write Article on Shortest Path Algorithm and link in this article

Problem Link:

https://leetcode.com/contest/weekly-contest-146/problems/shortest-path-with-alternating-colors/

Notes:

A very good Question indeed

1. Since we have to travel through alternate colored edges, so every node can have two distances, using blue or red edges. We cannot take minium distance at every step cuz, it might happen we might go over a node again after a cirle, but using different colored edge this time. so we need to maintain two distances for each node, one for each color.

2. Now comes issue of handling self loop or parallel edges. we will allow them as they might produce other colored path. instead of using visited array, we check if the distance we will get is smaller with this alternative route. if yes, we will allow self loop and paralle edges.

3. cu ^ cv checks if the current edge and previous edge were different colored.

Code:

    vector<vector<pair<int, int>>> adjList;
    vector<vector<int>> re, be;
    vector<pair<int, int>> dist;
    
    void buildGraph() {

        for (int i=0; i<re.size(); ++i) {
            adjList[re[i][0]].push_back({re[i][1], 0});
        }
        for (int i=0; i<be.size(); ++i) {
            adjList[be[i][0]].push_back({be[i][1], 1});
        }
    }
     
    void bfs () {
        
        queue<pair<int, int>> q;
        q.push({0, 0});
        q.push({0, 1});
        
        while(!q.empty()) {
            auto qf = q.front(); q.pop();
            int nv = qf.first;
            int cv = qf.second;

            for (auto &pu: adjList[nv]) {
                int nu = pu.first;
                int cu = pu.second;

                if (cu^cv && cv == 0 && dist[nu].first > dist[nv].second + 1) {
                    dist[nu].first = dist[nv].second + 1;
                    q.push(pu);
                }
                if (cu^cv && cv == 1 && dist[nu].second > dist[nv].first + 1) {
                    dist[nu].second = dist[nv].first + 1;
                    q.push(pu);
                }
            }
        }
    }
    
    // colors, red = 0, blue = 1.
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
        
        adjList = vector<vector<pair<int, int>>> (n);
        re = red_edges;
        be = blue_edges;
        buildGraph();
        dist = vector<pair<int, int>> (n, {INT_MAX, INT_MAX});
        dist[0] = {0, 0};
        bfs ();
        vector<int> ans(n);
        for (int i=0; i<n; ++i) {
            ans[i] = min (dist[i].first, dist[i].second);
            if (ans[i] == INT_MAX)  ans[i] = -1;
        }
        return ans;
    }