堆优化Dijkstra+向前星存图+超级起点/终点（牛客——星球游戏题解）

朴灿烈づ我的快乐病毒、 2023-03-01 13:26 5阅读 0赞

#  堆优化Dijkstra+向前星存图+超级起点/终点（牛客——星球游戏题解） #

[题目链接][Link 1]

#### 题意 ####

n个结点，m条边构成的图，其中牛牛有一定数量的点，牛妹也有一定数量的点，现在问从牛牛中任选一点到牛妹的任意一点的最短距离是多少？  
其中给定牛牛拥有的点数，牛妹拥有的点数，给出相应的图结构，已经图的节点数。

#### 题解 ####

考虑这个问题，从牛牛中任选一点到牛妹的任意一点的最短距离，显然是考虑最短路算法（**Dijkstra即可**）但是如果朴素的Dijkstra的话肯定会超时，于是考虑**堆优化的Dijkstra算法**，同时图比较大，于是采用**向前星存图**。

然后再想，是不是需要跑p遍dijkstra呢（p为牛牛的结点数），显然这样是没有必要的。  
**直接设一不存在的结点为终点，例如0，向牛牛所拥有的所有点建单向边，边的权值为0；  
设一不存在的点为终点，例如：n+1，牛妹所拥有的所有点向设的点建单向边，边的权值为0。  
类似于超级起点和超级终点。**

于是直接对超级起点跑一遍Dijkstra即可。

#### AC代码（cpp） ####

class Solution {
        
    static const int maxn=1e5+5;
    static const int maxm=5e5+5;
    static const int inf=0x3f3f3f3f;
    struct e{
        
        int to,nxt,val;
    }edge[maxm];
    int head[maxn],tot;
    int dis[maxn],vis[maxn];
    struct node{
        
        int index,dist;
        bool operator <(const node &b) const{
        
            return dist>b.dist;
        }
    };
    public:
        void init(){
        
            memset(head,-1,sizeof(head));
            tot=0;
        }
        void add(int u,int v,int c){
        
            edge[++tot].to=v;
            edge[tot].val=c;
            edge[tot].nxt=head[u];
            head[u]=tot;
        }
        int dijsktra(int s,int e,int n){
        
            memset(dis,inf,sizeof(dis));
            memset(vis,0,sizeof(vis));
            dis[s]=0;
            priority_queue<node> q;
            q.push(node{
        s,0});
            while(!q.empty()){
        
                node x=q.top();
                q.pop();
                int u=x.index;
                if(vis[u]) continue;
                vis[u]=1;
                for(int i=head[u];i!=-1;i=edge[i].nxt){
        
                    int v=edge[i].to,c=edge[i].val;
                    if(dis[v]>dis[u]+c){
        
                        dis[v]=dis[u]+c;
                        q.push(node{
        v,dis[v]});
                    }
                }
            }
            return dis[e];
        }
        /**
         *
         * @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
            init();
            int s=0,e=nn+1;
            for(int i=0;i<niuniu.size();i++){
        
                add(s,niuniu[i],0);
            }
            for(int i=0;i<niumei.size();i++){
        
                add(niumei[i],e,0);
            }
            for(int i=0;i<path.size();i++){
        
                int u=path[i][0],v=path[i][1],c=path[i][2];
                //cout<<u<<' '<<v<<' '<<c<<endl;
                add(u,v,c);add(v,u,c);
            }
            int ans=dijsktra(s,e,nn);
            if(ans==inf) return -1;
            return ans;
        }
    };

[Link 1]: https://ac.nowcoder.com/acm/contest/6629/C