题目描述

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

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

算法一：暴力+最短路径

算法思路

• 一个很显然很暴力的思路，将牛牛统治的每一颗星球，都跑一次最短路径
• 然后每次最短路径中，再选择到牛妹占领的星球距离最短的，设置为当次的最短距离
• 这样总共跑p次最短路径就可以得到答案
• 我这边代码写的是SPFA，当然用Dijk写也是一样的（毕竟都是超时

  代码实现

  typedef pair<int, int> PII;
  #define pb push_back
  #define x first
  #define y second
  const int N = 1e5 + 10;
  class Solution
  {
  public:
    vector<PII> v[N];//邻接表 
    int SPFA(vector<int> &Q,int &n,int &st){//SPFA求最短路（当然用Dijstra也行） 
        queue<int> q;
        q.push(st);//放入起点 
        bool vis[N];//标记，是否在队列中 
        int dis[N];//到起点的距离 
        memset(dis,0x3f,sizeof dis);//初始化都是无穷大 
        memset(vis,0,sizeof vis);//初始都不在队列中 
        vis[st]=1;//起点已经入队 
        dis[st]=0;//自己到自己的距离为0 
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(auto it:v[u]){//通过邻接表访问u的邻居 
                if(dis[u]+it.y<dis[it.x]){//可以对边进行松弛操作 
                    dis[it.x]=dis[u]+it.y;
                    if(!vis[it.x]){//不在队列中 ，则将其放入队列中 
                        vis[it.x]=1; 
                        q.push(it.x);
                    }
                }
            }
        }
        int res=dis[n+2];//赋值为无穷大 
        for(auto it:Q){
            res=min(res,dis[it]);//求牛牛当前起点到牛妹的所有星球之一的最短距离 
        } 
        return res;
    }
    int Length(vector<int> &P, vector<int> &Q, vector<vector<int>> &path, int n)
    {
        for (int i = 0; i < path.size(); i++)
        {
            v[path[i][0]].pb({path[i][1],path[i][2]});//建图 
            v[path[i][1]].pb({path[i][0],path[i][2]});
        }
        int ans=0x3f3f3f3f,tmp;
        for(auto it:P){
            ans=min(ans,SPFA(Q,n,it));//每个起点都跑一次SPFA最短路 
        }
        if(ans==0x3f3f3f3f)return -1;//如果不连通 
        return ans;
    }
  };

  复杂度分析

• 时间复杂度，对于最短路径，SPFA最短路平均情况是,为常数，但是如果出题人故意卡你，可能可以达到，除非打的是竞赛不然这种情况很少，如果用Dijkstra堆优化复杂度稳定,打竞赛的话推荐Dijk堆优化。建图为，每次跑完SPFA都要再扫描一次终点，为,最短路共需要跑p次，总得时间复杂度为

  算法二：超级源点汇点+最短路径

  算法思路

• 在上面的过程中我们会发现，我们的SPFA过程中，会跑过很多重复的路径
• 反复做这些过程，不仅耗时间，而且耗费空间
• 所以我们有什么办法能省去这些过程呢？如何优化成了本题的重点
• 我们假设图为这样
  
• 绿色代表牛牛的星球，红色代表牛妹的星球
• 实际上我们可以这样理解，既然这些星球都是由我统治的，我在星球与星球之间安装一个“虫洞传送装置”不过分吧？
• 即绿色的星球两两之间，都可以建立花费为0的连边，红色的星球两两之间也可以
• 为什么可以这样做？
• 反证法，如果这是我们最后所求的最短路径的话，那么这条路径上除了起点和终点为，都只有黑色节点
• 如下图，假设我们求出来的答案是这样(1-->3)，显然我们会发现一开始从2出发，会更优
  
• 即，原来的路径上面如果存在非黑色节点，那么原来的最短路径一定能被更短的路径替代
• 这样建立新图之后，如果初始选择的源点跑出来的不是答案的最短路径，我们以及可以花费“0”（无条件转移到其他绿色节点），跑新的答案，这样就省略的重复求最短路径的过程
• 这样我们只需要同样的非黑色节点里面，两两建边（完全子图），最后只跑一次最短路径即可算出答案

再次优化

• 我们会发现只需要保证，同色的非黑色节点之间的联通性即可以，所以不需要建立完全子图，只需要建立成一棵树即可，这样建立边的时间有可以少很多

  方案一

• P中的第一个节点到P其后的每一个节点都建立一个权值为0的边，即“菊花图”
  

  方案二

• P中下标前后相邻的两个建立权值为0的连边，即“链表“

方案三

• 定义一个超级源点，编号为0,（图中没有用过），建立它和P中每个数权值为0的连边
  

• 此处我们选择方案三，上面两种也是可行的，但是方案三比较好写，代码量也比较小一点

• (对于红色节点Q的实现方式同理)

代码实现

typedef pair<int, int> PII;
#define pb push_back
#define x first
#define y second
const int N = 1e5 + 10;
class Solution
{
public:
    vector<PII> v[N];
    int SPFA(int n){
        queue<int> q;
        q.push(0);//放入起点 
        bool vis[N];//标记，是否在队列中 
        int dis[N];//到起点的距离 
        memset(dis,0x3f,sizeof dis);//初始化都是无穷大 
        memset(vis,0,sizeof vis);//初始都不在队列中 
        vis[0]=1;//起点已经入队 
        dis[0]=0;//超级源点自己到自己的距离为0 
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(auto it:v[u]){//通过邻接表访问u的邻居 
                if(dis[u]+it.y<dis[it.x]){//如果可以对边进行松弛操作
                    dis[it.x]=dis[u]+it.y;
                    if(!vis[it.x]){//不在队列中 ，则将其放入队列中 
                        vis[it.x]=1;
                        q.push(it.x);
                    }
                }
            }
        }
        if(dis[n+1]==dis[n+2])return -1;//如果图不连通
        return dis[n+1];
    }
    int Length(vector<int> &P, vector<int> &Q, vector<vector<int>> &path, int n)
    {
        for (auto it : P)//建立超级源点到其他起点的连边
        {
            v[it].pb({0, 0});
            v[0].pb({it, 0});
        }
        for (auto it : Q)//建立超级汇点到其他终点的连边
        {
            v[it].pb({n + 1, 0});
            v[n + 1].pb({it, 0});
        }
        for (int i = 0; i < path.size(); i++)//初始建立图
        {
            v[path[i][0]].pb({path[i][1],path[i][2]});
            v[path[i][1]].pb({path[i][0],path[i][2]});
        }
        return SPFA(n);//从超级源点开始跑最短路径
    }
};

复杂度分析

• 时间复杂度，对于最短路径，SPFA最短路平均情况是,为常数。建图为，建立超级源点汇点的连边为，总得时间复杂度为
• 空间复杂度，定义了一个队列，dis,vis数组，为