题意理解

n个星球可以看作n个结点，之间有零到多条无向边，牛牛和牛妹占领的星球可以看作两个点集。题目要求，从点集A中的某点到点集B中某点的所需要的最短距离。

方法一

最短路径算法有多种。本题中没有给定起点和终点，而是一个起点的集合A和终点的集合B，所以使用Floryd算法，求得所有结点之间的最短路径，再遍历起点在A终点在B的情况，找出其中的最短路径长度。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param serialP intvector 牛牛占领的p个星球的编号
     * @param serialQ intvector 牛妹占领的q个星球的编号
     * @param path intvector<vector<>> m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
     * @param nn int 星球个数n
     * @return int
     */
    const int N = 1e5 + 10;



    int Length(vector<int>& serialP, vector<int>& serialQ, vector<vector<int> >& path, int nn) {
        // write code here
        vector<int> min_path[N];//记录星球之间的最短路径
        int path_num = path.size();
        int minm = 100001;
        for (int i=1;i<=nn;i++)
        {
            for (int j=1;j<=i;j++)
            {
                min_path[i].push_back(100001);
            }
        }
        for (int i=0;i<path_num;i++)
        {
            int line = max(path[i][0],path[i][1]);
            int row = min(path[i][0],path[i][1]);
            min_path[line][row] = min(min_path[line][row],path[i][2]);
        }
        //floryd算法
        for (int k=1;k<=nn;k++)
        {
            for (int i=1;i<=nn;i++)
            {
                for (int j=1;j<i;j++)
                {
                    if (i!=k && j!=k)
                        min_path[i][j] = min(min_path[i][j],min_path[max(i,k)][min(i,k)]+min_path[max(k,j)][min(k,j)]);
                }
            }
        }
        //遍历起点集A和终点集B，找出最短路径
        for (int i=0;i<serialP.size();i++)
        {
            for (int j=0;j<serialQ.size();j++)
            {
                int line = max(serialP[i],serialQ[j]);
                int row = min(serialP[i],serialQ[j]);
                if (minm > min_path[line][row])
                {
                    minm = min_path[line][row];
                    cout<<line<<' '<<row<<' '<<min_path[line][row]<<endl;
                }
            }
        }
        if (minm == 100001) return -1;
        else return minm;
    }
};

时间复杂度：。floryd算法的时间复杂度为N的3次方，会导致超时。
空间复杂度：。使用了一个邻接表存储路径，M为边的条数，会导致内存超出。

方法二

floryd算法的时间复杂度过高，而Dijkstra算法的时间复杂度只有，所以可以考虑将多源最短路径问题转换为已知起点和终点的对应问题。这里常见的方法就是添加超级源点。
我们添加一个起点s，和点集A中每个点之间有一条长度为0的路径，与其余点无连接；同理添加终点e，和点集B相连；求出由s到e的最短路径长度即可。
示意图如下：

但是使用简单的Dijkstra算法还是会导致超时，需要使用堆来优化内循环（找最小的dis[i]）。
具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param serialP intvector 牛牛占领的p个星球的编号
     * @param serialQ intvector 牛妹占领的q个星球的编号
     * @param path intvector<vector<>> m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
     * @param nn int 星球个数n
     * @return int
     */
    const int N = 2e5 + 10;
    int cnt,head[500020];
    struct Edge{
        int to,next,len;
    }edge[500020];
    void add_edge(int from,int to,int w)
    {
        edge[++cnt].len=w;
        edge[cnt].to=to;
        edge[cnt].next=head[from];
        head[from]=cnt;
    }
    struct qbase{
        int key,value;
        //要设置成最小堆
        bool operator < (const qbase &other) const
        {
            return value>other.value;
        }
    };

    int Length(vector<int>& serialP, vector<int>& serialQ, vector<vector<int> >& path, int nn) {
        // write code here
        int end = nn+1;
        bool haveGone[N];
        priority_queue<qbase> q;//维护一个优先队列，来寻找下一个结点
        int dis[N],tag;
        dis[0] = 0;
        //初始化
        for (int i=0;i<path.size();i++)
        {
            add_edge(path[i][0],path[i][1],path[i][2]);
            add_edge(path[i][1],path[i][0],path[i][2]);
        }
        for (int i=1;i<=end;i++)
        {
            dis[i] = 100001;
            haveGone[i] = false;
        }
        for (int i=0;i<serialP.size();i++)
        {
            add_edge(0,serialP[i],0);
        }
        for (int i=0;i<serialQ.size();i++)
        {
            add_edge(serialQ[i],end,0);
        }
        //经过堆优化的Dijkstra算法
        q.push((qbase){0,0});
        while (!q.empty())
        {
            tag = q.top().key;
            q.pop();
            if (haveGone[tag]) continue;
            haveGone[tag] = true;
            int j = head[tag];

            for(;j;j=edge[j].next)
            {
                int temp = edge[j].to;
                if (dis[temp]>dis[tag] + edge[j].len)
                {
                    dis[temp] = dis[tag] + edge[j].len;
                    q.push((qbase){temp,dis[temp]});
                }
            }
        }
        if (dis[end]==100001) return -1;
        else return(dis[end]);
    }
};

时间复杂度：。在寻找当前最小的dis[i]的时候使用的是最小堆，所以仅用了的时间。
空间复杂度：。使用了多个长度与边或者结点个数相关的数组来存储信息。