题解 | #托米去购物#

描述

牛牛和牛妹在进行一场星球模拟游戏，游戏规则如下：

游戏地图内共有n个星球，共有m条隧道连接这些星球。每条隧道都是双向的，每两个星球间不一定只有一条隧道。现在牛牛占领了这n个星球中的p个星球，牛妹占领了这n个星球中的q的星球（每个星球最多只能被一个人占领）。现在牛牛想知道他占领的p个星球中任意一个星球，到牛妹占领的q个星球中任意一个星球，这两个星球的最短距离是多少。

示例1
输入：

[1],[3,4],[[1,2,7],[2,3,6],[3,4,2],[1,3,11],[2,4,3]],4
返回值：
10
说明：
距离最近的牛牛星和牛妹星是1和4，他们之间的距离为10

示例2
输入：

[1],[2],[],2
返回值：
-1
说明：
所有的牛牛星和牛妹星都不联通，故输出-1

备注：
对于50%的数据：
2\leq n\leq 100,0\leq m\leq 200,1\leq p\leq 5,1\leq q\leq 5,p+q\leq n,1\leq wi\leq 1e42≤n≤100,0≤m≤200,1≤p≤5,1≤q≤5,p+q≤n,1≤wi≤1e4
对于100%的数据：
2\leq n\leq 1e5,0\leq m\leq 2e5,1\leq p\leq 1e5,1\leq q\leq 1e5,p+q\leq n,min(p,q)\leq 10,1\leq wi\leq 1e42≤n≤1e5,0≤m≤2e5,1≤p≤1e5,1≤q≤1e5,p+q≤n,min(p,q)≤10,1≤wi≤1e4
相关参数意义如下
serialP 牛牛占领的p个星球的编号
serialQ 牛妹占领的q个星球的编号
path m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
nn int整型 星球个数n

解题思路：
多源最短路，只需添加一个超级源点以及一个超级终点便可当作单源最短路

AC代码：

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 Inf = 0x3f3f3f3f;
    struct num{
        int e,w,ne;
    }edge[(int)1e6+10];
    int len;
    int h[(int)1e5+10];
    int dis[(int)1e5+10];
    bool vis[(int)1e5+10];

    void add(int a,int b,int c){
        edge[len].e=b;
        edge[len].w=c;
        edge[len].ne=h[a];
        h[a]=len++;
    }

    void dijk(int u){
        memset(dis,Inf,sizeof(dis));
        memset(vis,false,sizeof(vis));
        dis[u]=0;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>Q;
        Q.push({0,u});
        while(Q.size()){
            auto t =Q.top();
            Q.pop();
            int v=t.second;
            if(vis[v]){
                continue;
            }
            vis[v]=true;
            for(int i=h[v];~i;i=edge[i].ne){
                int j=edge[i].e;
                if(dis[j]>dis[v]+edge[i].w){
                    dis[j]=dis[v]+edge[i].w;
                    Q.push({dis[j],j});
                }
            }
        }
    }
    int Length(vector<int>& serialP, vector<int>& serialQ, vector<vector<int> >& path, int nn) {
        // write code here
        memset(h,-1,sizeof(h));
        len=0;
        for(int i=0;i<path.size();i++){
            add(path[i][0],path[i][1],path[i][2]);
            add(path[i][1],path[i][0],path[i][2]);
        }
        for(int i=0;i<serialP.size();i++){
            add(0,serialP[i],0);
        }
        for(int i=0;i<serialQ.size();i++){
            add(serialQ[i],nn+1,0);
        }
        dijk(0);
        if(dis[nn+1]==Inf){
            return -1;
        }
        else{
            return dis[nn+1];
        }
    }
};