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

牛客编程巅峰赛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; }
    };
上一篇:UVa 11374 - Airport Express ( dijkstra预处理 )


下一篇:利用分支限界法求解单源最短路(Dijkstra)问题