星球游戏题解

50分解法

由于n很小只有100，我们可以用建一个n^2的矩阵，用floyd，dijkstra或者spfa等等最短路的相关算法跑出每个点对见的最短距离，然后再判断两个点是不是一个是牛牛占领的星求，一个是牛妹占领的星球即可。时间复杂度和空间复杂度根据选择的最短路算法而不同，如果使用floyd时间复杂度为o(n^3)，空间复杂度为o（n^2）。

100分解法

这里提供两种做法

1.跑min（p，q）次dijkstra算法，时间复杂度为o（nlogn*min(p,q)），空间复杂度o（n+m）

虽然p+q的值很大，但是p和q中小的值并不大，我们可以分别以p和q中少的点为起点跑最短路，然后每次跑完最短路判断这个点对应的点是否为另一个人占领的星球，如果是执行 ans=min(ans,dis[i])。代码如下：

完善核心代码模式代码：

#define MAX 1000000001
const int maxn=100005;
int num[maxn];
int n,s;
int uss[maxn];
struct edge{int to;int cost;
 bool operator < (const edge & a) const
     {
        return cost> a.cost;
     }
};
vector<edge>g[maxn];
priority_queue<edge> vis;
void dijkstra()
{
    int i;
    for(i=1;i<=n;i++)
      num[i]=MAX;
      num[s]=0;
      vis.push((edge){s,0});
    while(!vis.empty())
    {
        edge node=vis.top();
        vis.pop();
        for(i=0;i<g[node.to].size();i++)
            if(num[g[node.to][i].to]>node.cost+g[node.to][i].cost)
                {
                   num[g[node.to][i].to]=node.cost+g[node.to][i].cost;
                   vis.push((edge){g[node.to][i].to,num[g[node.to][i].to]});
                }
    }
}
class Solution {
public:
    /**
     * 
     * @param niuniu int整型vector 牛牛占领的p个星球的编号
     * @param niumei int整型vector 牛妹占领的q个星球的编号
     * @param path int整型vector<vector<>> m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
     * @param nn int整型 星球个数n
     * @return int整型
     */
    int Length(vector<int>& niuniu, vector<int>& niumei, vector<vector<int> >& path, int nn) {
        // write code here
        n=nn;
        edge tmp;
        stack<int >sta;
        if(niuniu.size()<=10)
        {
            for(int i=0;i<niuniu.size();i++)
            {
                sta.push(niuniu[i]);
            }
            for(int i=0;i<niumei.size();i++)
            {
                uss[niumei[i]]=1;
            }
        }
        else
        {
            for(int i=0;i<niuniu.size();i++)
            {
                uss[niuniu[i]]=1;
            }
            for(int i=0;i<niumei.size();i++)
            {
                sta.push(niumei[i]);
            }
        }
        for(int i=0;i<path.size();i++)
        {
            int x=path[i][0];
            tmp.to=path[i][1];
            tmp.cost=path[i][2];
            g[x].push_back(tmp);
            swap(tmp.to,x);
            g[x].push_back(tmp);
        }
        int ans=MAX;
        while(!sta.empty())
        {
            s=sta.top();
            sta.pop();
            dijkstra();
            for(int i=1;i<=n;i++)
            {
                if(uss[i])
                {
                    ans=min(ans,num[i]);
                }
            }
        }
        if(ans==MAX)ans=-1;
        return ans;
    }
};

2.只跑一次最短路的方法

当然，这道题还有更优的做法。第一个做法之所以可行是因为min（p,q）<=10，其实即使删除这个条件，这道题也是可做的，而且只需要跑一次最短路，显然时间复杂度更低，为o（nlogn），空间复杂度同为o（n+m）。具体实现方法是建立一个超级起点（这个思想有点类似于网络流），我们使这个起点向所有牛牛星建立一条权值为0的边，然后跑一次dijkstra，对于每个牛妹星执行 ans=min(ans,dis[i])即可，代码如下：

完善核心代码模式代码：

const int maxn = 200005;
const int maxm = 800005;
int n,m,s,tol,head[maxn],dis[maxn];
struct edge{int to,w,next;}g[maxm];
struct node
{
    int u,d;
    friend bool operator <(node a,node b)
    {
        return a.d>b.d;
    }
};
void add(int u,int v,int w)
{
    g[tol].to = v;
    g[tol].w = w;
    g[tol].next = head[u];
    head[u] = tol++;
}
void dijkstra(int s)
{
    for(int i = 1;i<=n;i++) dis[i] = 0x3f3f3f3f;
    dis[s] = 0;
    priority_queue<node>q;
    q.push((node){s,0});
    while(!q.empty())
    {
        node p = q.top();
        q.pop();
        int u = p.u,d = p.d;
        if(d!=dis[u]) continue;
        for(int i = head[u];i!=-1;i = g[i].next)
        {
            int v = g[i].to;
            int w = g[i].w;
            if(dis[u]+w<dis[v])
            {
                dis[v] = dis[u] + w;
                q.push((node){v,dis[v]});
            }
        }
    }
}
bool vis[maxn];
class Solution {
public:
    /**
     * 
     * @param niuniu int整型vector 牛牛占领的p个星球的编号
     * @param niumei int整型vector 牛妹占领的q个星球的编号
     * @param path int整型vector<vector<>> m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
     * @param nn int整型 星球个数n
     * @return int整型
     */
    int Length(vector<int>& niuniu, vector<int>& niumei, vector<vector<int> >& path, int nn) {
        // write code here
        n=nn+1;
        memset(head,-1,sizeof(head));
        for(int i=0;i<niuniu.size();i++)
        {
            add(n,niuniu[i],0);
        }
        for(int i=0;i<niumei.size();i++)
        {
             vis[niumei[i]]=1;
        }

        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]);
        }
        dijkstra(n);
         int ans = 0x3f3f3f3f;
        for(int i = 1;i<=n;i++) {
            if(vis[i]) ans = min(ans,dis[i]);
        }
        if(ans==0x3f3f3f3f)ans=-1;
        return ans;
    }
};