牛客编程巅峰赛S1第6场 - 黄金&钻石&王者 C.星球游戏 (单源最短路,Dijkstra)

题意:有\(n\)个点,\(m\)条双向边,两个方向的权值都是相等的,可以从\(A\)中的某个点出发走到\(B\)中的某个点,求所有路径中的最短距离,如果A和B中没有点联通,则输出\(-1\).
题解:感觉是个阅读理解啊,题目看懂了就是个裸的单源最短路,我们首先将牛牛的所有星球初始化作为起点,然后建边跑个dijkstra,最后再枚举牛妹的星球维护一个最小值即可.

代码:

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整型

     */

    struct misaka{

        int out;

        int val;

    }e;

    int dis[1000000];

    bool st[1000000];

    vector<misaka> v[1000000];

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> h;

    void dijkstra(){

        while(!h.empty()){

            auto tmp=h.top();

            h.pop();

            int num=tmp.second;

            int dist=tmp.first;

            if(st[num]) continue;

            st[num]=true;

            for(auto w:v[num]){

                int node=w.out;

                if(dis[node]>w.val+dist){

                    dis[node]=w.val+dist;

                    h.push({dis[node],node});

                }

            }

        }

    }

     int Length(vector<int>& niuniu, vector<int>& niumei, vector<vector<int> >& path, int nn) {

        // write code here

        memset(dis,0x3f3f3f3f,sizeof(dis));

        memset(st,false,sizeof(st));

        for(auto w:niuniu){

            dis[w]=0;

            h.push({0,w});

        }

        for(auto w:path){

            int a=w[0];

            int b=w[1];

            int val=w[2];

            e.out=b,e.val=val;

            v[a].push_back(e);

            e.out=a;

            v[b].push_back(e);

        }

        dijkstra();

        int ans=0x3f3f3f3f;

        for(auto w:niumei){

            ans=min(ans,dis[w]);

        }

        if(ans==0x3f3f3f3f) ans=-1;

        return ans;

    }

};

巴特西

牛客编程巅峰赛S1第6场 - 黄金&钻石&王者 C.星球游戏 (单源最短路,Dijkstra)

最新文章

热门文章