1129. 颜色交替的最短路径

╰半橙微兮° 2023-10-04 18:56 11阅读 0赞

在一个有向图中，节点分别标记为 0, 1, ..., n-1。图中每条边为红色或者蓝色，且存在自环或平行边。

red\_edges 中的每一个 \[i, j\] 对表示从节点 i 到节点 j 的红色有向边。类似地，blue\_edges 中的每一个 \[i, j\] 对表示从节点 i 到节点 j 的蓝色有向边。

返回长度为 n 的数组 answer，其中 answer\[X\] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer\[x\] = -1。

示例 1：

输入：n = 3, red\_edges = \[\[0,1\],\[1,2\]\], blue\_edges = \[\]  
输出：\[0,1,-1\]  
示例 2：

输入：n = 3, red\_edges = \[\[0,1\]\], blue\_edges = \[\[2,1\]\]  
输出：\[0,1,-1\]  
示例 3：

输入：n = 3, red\_edges = \[\[1,0\]\], blue\_edges = \[\[2,1\]\]  
输出：\[0,-1,-1\]  
示例 4：

输入：n = 3, red\_edges = \[\[0,1\]\], blue\_edges = \[\[1,2\]\]  
输出：\[0,1,2\]  
示例 5：

输入：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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/shortest-path-with-alternating-colors  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## JAVA\[1129\] 简单思路 ##

#### 解题思路 ####

两次DFS就完事了, 交替遍历边

额, 写的不是太简洁

class Solution {
        List<Integer>[] rlist, blist;
        int[] rStep, bStep;
        public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
            // 最短路径, 可以 BFS, 也可以DFS
            // 貌似这题 dfs 更合适
            // 邻接表用list存储
            int inf = 128;
            rlist = new ArrayList[n];
            blist = new ArrayList[n];
            rStep = new int[n];
            bStep = new int[n];
            for (int i = 1; i < n; ++i) rStep[i] = bStep[i] = inf;
            for (int i = 0; i < n; ++i) {
                rlist[i] = new ArrayList<Integer>();
                blist[i] = new ArrayList<Integer>();
            }
            for (int[] edge : redEdges) rlist[edge[0]].add(edge[1]);
            for (int[] edge : blueEdges) blist[edge[0]].add(edge[1]);
            dfs(0, 0, true);
            dfs(0, 0, false);
            int[] ans = new int[n];
            for (int i = 1; i < n; ++i) {
                int step = Math.min(rStep[i], bStep[i]);
                if (step == inf) ans[i] = -1;
                else ans[i] = step;
            }
            return ans;
        }
        void dfs(int x, int step, boolean flag) { // flag : ture 当前该遍历红色边, false 相反
            if (flag) {
                for (int i : rlist[x]) {
                    if (rStep[i] <= step + 1) continue; // 当前可以更快到达, 剪枝
                    rStep[i] = step + 1;
                    dfs(i, step + 1, false);
                }
            }
            else {
                for (int i : blist[x]) {
                    if (bStep[i] <= step + 1) continue; // 当前可以更快到达, 剪枝
                    bStep[i] = step + 1;
                    dfs(i, step + 1, true);
                }
            }
        }
    }
    
    作者：wuzhenyu
    链接：https://leetcode.cn/problems/shortest-path-with-alternating-colors/solution/java-by-wuzhenyu-pn8k/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

颜色交替的最短路径  
  
BFS应用和去重访问的设计  
  
本题与最经典基本的BFS的区别是比较明显的，经典有向无权图BFS求最短路就是利用邻接矩阵或者邻接表，配合dis数组，可能还会有visited数组来去重访问，利用queue进行广度优先搜索更新dis就可以了。那么本题的区别就是要求在红蓝边交替进行遍历的条件限制下进行，思路很显然就是在原来经典BFS的基础上加上红蓝标记就行了，编码中就利用0和1在作为标记位就行了。剩下的就是去重的思考了。  
  
经典BFS去重就是visited表示，其实dis数组更新也能过实现去重的效果，是遇到一个节点就放进visited数组中，而本题是不能这样处理的，因为红蓝边的交替导致可以重复访问一个点来改变红蓝交替的路线来抵达目标点，那么关键的就是抓住这个区别，我们给普通的一维visited数组加个0和1标记位变成二维visited数组，当既从红色边访问过这个点，又从蓝色边访问过这个点，这个点就可以不用再访问了。而可以保证这样做的原因就是很纯粹的，就是基于经典BFS思路和本题的区别所在。因为允许重复访问一个节点的根本原因就是为了改变红蓝访问路线，所以在基于这样的充分理解下，本题就可以很轻松地写出来了。

代码如下：

作者：bai-mu-ying-li-Dra-ENIAC  
链接：https://leetcode.cn/problems/shortest-path-with-alternating-colors/solution/by-bai-mu-ying-li-dra-eniac-jehj/  
来源：力扣（LeetCode）  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public:
        vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
            vector<vector<pair<int,int>>> graph(n);
            vector<vector<int>> visited(n,vector<int>(2,0));
            //0表示red 1表示blue
            for(auto& edge:redEdges){
                int from=edge[0];
                int to=edge[1];
                graph[from].push_back({to,0});
            }
            for(auto& edge:blueEdges){
                int from=edge[0];
                int to=edge[1];
                graph[from].push_back({to,1});
            }
            queue<vector<int>> q;
            vector<int> dis(n,INT_MAX);
            dis[0]=0;
            q.push({0,0,1});//节点 距离 颜色
            q.push({0,0,0});
            while(!q.empty()){
                auto it=q.front();
                int from=it[0];
                int distance=it[1];
                int col=it[2];
                q.pop();
                for(auto& [to,colour]:graph[from]){
                    if(colour==(!col) && !visited[to][colour]){
                        dis[to]=min(dis[to],distance+1);
                        q.push({to,distance+1,colour});
                        visited[to][colour]=1;
                    }
                }
            }
            for(int i=0;i<n;i++){
                if(dis[i]==INT_MAX)dis[i]=-1;
            }
            return dis;
        }
    };
    
    作者：bai-mu-ying-li-Dra-ENIAC
    链接：https://leetcode.cn/problems/shortest-path-with-alternating-colors/solution/by-bai-mu-ying-li-dra-eniac-jehj/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。