题解 | #星球游戏#

题意整理

• 有n个星球，星球之间通过m条隧道连接，牛牛占有p个星球，牛妹占有q个星球。
• 求从牛牛占有的星球到牛妹占有的星球需要走过的最短距离。

方法一（弗洛伊德算法）

1.解题思路

• 首先初始化一个二维数组dist，记录每个星球间的距离。
• 通过给定的隧道，给dist数组赋值。
• 走弗洛伊德算法，基本思想是三层循环，枚举中转点、起点和终点，遍历所有可能的情况，取最小距离。
• 计算完之后，列举牛牛的星球，以及牛妹的星球，计算从牛牛星球到牛妹星球的最短距离。

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param serialP int一维数组 牛牛占领的p个星球的编号
     * @param serialQ int一维数组 牛妹占领的q个星球的编号
     * @param path int二维数组 m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
     * @param nn int 星球个数n
     * @return int
     */
    //记录星球之间距离
    int[][] dist;
    //星球个数
    int nn;
    //最大Integer型整数的一半
    int INF=Integer.MAX_VALUE/2;
    public int Length (int[] serialP, int[] serialQ, int[][] path, int nn) {
        //初始化
        this.nn=nn;
        dist=new int[nn][nn];
        for(int i=0;i<nn;i++){
            for(int j=0;j<nn;j++){
                if(i!=j){
                    dist[i][j]=INF;
                }
            }
        }

        //将路径情况赋值到dist数组
        for(int i=0;i<path.length;i++){
            //如果两星球间有多条路径，选择最短的那条
            if(dist[path[i][0]-1][path[i][1]-1]!=0||dist[path[i][0]-1][path[i][1]-1]!=INF){
                dist[path[i][0]-1][path[i][1]-1]=Math.min(dist[path[i][0]-1][path[i][1]-1],path[i][2]);
                dist[path[i][1]-1][path[i][0]-1]=Math.min(dist[path[i][1]-1][path[i][0]-1],path[i][2]);
            }
            //如果只有一条路径，直接赋值
            else{
                dist[path[i][0]-1][path[i][1]-1]=path[i][2];
                dist[path[i][1]-1][path[i][0]-1]=path[i][2];
            }

        }
        //弗洛伊德算法计算所有点之间最短距离
        floyd();

        int min=INF;
        //取所有可能情况的最小值，作为最短距离
        for(int i=0;i<serialP.length;i++){
            for(int j=0;j<serialQ.length;j++){
                min=Math.min(min,dist[serialP[i]-1][serialQ[j]-1]);
            }
        }
        return min>=INF?-1:min;
    }

    //弗洛伊德算法
    private void floyd(){
        //选择中转点，计算起点经过中转点到达终点的所有情况
        for(int p=0;p<nn;p++){
            for(int i=0;i<nn;i++){
                for(int j=0;j<nn;j++){
                    dist[i][j]=Math.min(dist[i][j],dist[i][p]+dist[p][j]);
                }
            }
        }
    }
}

3.复杂度分析

• 时间复杂度：假设星球个数为n，隧道数为m，弗洛伊德算法需要执行三层循环，总共，同时还需要线性遍历所有的隧道，共m次，所以最终的时间复杂度为。
• 空间复杂度：需要额外大小为的dist数组，所以空间复杂度为。

方法二（广度优先搜索）

1.解题思路

• 首先将星球间连接情况统计在一个邻接表里，邻接表里元素是一个型集合,第一个值记录目标星球，第二个值记录到目标星球的距离。
• 然后新增一个0号星球，并且将牛牛占领的星球与之相连，距离为0；新增一个号星球，并且将牛妹占领的星球与之相连，距离为0。
• 通过广度优先搜索，统计每个星球到0号星球的距离的最小值。
• 最后号星球到0号星球距离最小值即是所求最小距离。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param serialP int一维数组 牛牛占领的p个星球的编号
     * @param serialQ int一维数组 牛妹占领的q个星球的编号
     * @param path int二维数组 m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
     * @param nn int 星球个数n
     * @return int
     */
    //最大Integer型整数
    int INF=Integer.MAX_VALUE;
    //邻接表
    List<List<int[]>> graph;
    //星球个数
    int nn;
    //距离数组，记录某个星球到起点星球的距离
    int[] dist;
    //标记数组
    boolean[] v;
    public int Length (int[] serialP, int[] serialQ, int[][] path, int nn) {
        //初始化
        this.nn=nn;
        graph=new ArrayList<>();
        for(int i=0;i<nn+2;i++){
            graph.add(new ArrayList<>());
        }

        //给邻接表赋值
        for(int i=0;i<path.length;i++){
            int u=path[i][0];
            int v=path[i][1];
            int w=path[i][2];
            graph.get(u).add(new int[]{v,w});
            graph.get(v).add(new int[]{u,w});
        }

        //新增一个0号星球，并且将牛牛占领的星球与之相连，距离为0
        for(int i=0;i<serialP.length;i++){
            graph.get(0).add(new int[]{serialP[i],0});
            graph.get(serialP[i]).add(new int[]{0,0});
        }

        //新增一个nn+1号星球，并且将牛妹占领的星球与之相连，距离为0
        for(int i=0;i<serialQ.length;i++){
            graph.get(nn+1).add(new int[]{serialQ[i],0});
            graph.get(serialQ[i]).add(new int[]{nn+1,0});
        }

        dist=new int[nn+2];
        v=new boolean[nn+2];
        Arrays.fill(dist,INF);
        //起点为0号星球，所以距离为0
        dist[0]=0;
        v[0]=true;
        //进行bfs搜索
        bfs();
        return dist[nn+1]==INF?-1:dist[nn+1];
    }

    private void bfs(){
        Queue<Integer> queue=new LinkedList<>();
        //起点星球入队
        queue.offer(0);

        while(!queue.isEmpty()){
            //弹出当前星球
            int cur=queue.poll();
            //找到所有相连星球
            for(int[] node:graph.get(cur)){
                //如果距离更小，则更新当前相连星球到起点的距离
                dist[node[0]]=Math.min(dist[node[0]],dist[cur]+node[1]);
                //如果未被访问，则入队继续遍历
                if(!v[node[0]]){
                    v[node[0]]=true;
                    queue.offer(node[0]);
                }
            }
        }
    }
}

3.复杂度分析

• 时间复杂度：最多有n个星球入队，假设入队之后每个星球的隧道数平均为k，则bfs需要搜素次，算上给邻接表赋值的时间复杂度，最终的时间复杂度是。
• 空间复杂度：需要额外大小为的dist数组，以及大小为的邻接表，所以空间复杂度为。