正文

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

IP云
IP云V管理员/6 阅读
08/14
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

  • 题意:有\(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)的更多相关文章

  1. 牛客编程巅峰赛S1第6场 - 黄金&amp&semi;钻石&amp&semi;王者 B&period;牛牛摆放花 &lpar;贪心&rpar;

    题意;将一组数重新排序,使得相邻两个数之间的最大差值最小. 题解:贪心,现将所有数sort一下,然后正向遍历,将数分配到新数组的两端,然后再遍历一次维护一个最大值即可. 代码: class Solut ...

  2. 牛客编程巅峰赛S1第6场 - 黄金&amp&semi;钻石&amp&semi;王者 A&period;牛牛爱奇数 &lpar;模拟&rpar;

    题意:有一组数,每次将所有相等的偶数/2,求最少操作多少次使得所有数变成奇数. 题解:用桶标记,将所有不同的偶数取出来,然后写个while模拟统计一下次数就行. 代码: class Solution ...

  3. 牛客编程巅峰赛S1第5场 - 黄金&amp&semi;钻石&amp&semi;王者 B&period;牛牛的字符串 &lpar;DP&rpar;

    题意:有一个字符串\(s\),我们可以选择\(s_{i}\),如果\(s_{i+k}>s_{i}\),那么就可以交换\(s_{i}\)和\(s_{i+k}\),问最多能够交换多少次. 题解:因为 ...

  4. 牛客编程巅峰赛S1第11场 - 黄金&amp&semi;钻石 C&period;牛牛找子集 &lpar;二分&rpar;

    题意:有一\(n\)个数,从中找数构成相同的子集,要求子集元素个数为\(k\),求构成子集个数最多的情况,输出子集(字典序最小). 题解:我们可以对子集的个数二分答案,首先用桶记录每个元素的个数,然后 ...

  5. 牛客编程巅峰赛S1第11场 - 黄金&amp&semi;钻石B&period;新集合&lpar;DFS&rpar;

    题意:有\([1,n]\)这\(n\)个数,构造集合,集合中不能包含\(u\)和\(v\),问最多能构造多少个集合. 题解:被这题卡了一整场.....以为是推公式,结果答案是暴搜? ​ 首先我们先用一 ...

  6. 牛客编程巅峰赛S1第11场 - 黄金&amp&semi;钻石A&period;牛牛的01游戏 &lpar;模拟栈&rpar;

    题意:有一个\(01\)串,两个相邻的\(0\)可以变成一个\(1\),两个相邻的\(1\)可以直接消除,问操作后的字符串. 题解:数组模拟栈直接撸,上代码吧. 代码: class Solution ...

  7. 牛客编程巅峰赛S1第5场 - 青铜&amp&semi;白银 C&period;排队 &lpar;优先队列&comma;归并排序&rpar;

    题意:有\(m\)个窗口,\(n\)个人排队,每个人都有各自的办理时间,只有办理完成窗口才能空出来,后面的人开始办理,求有多少人比后面的人开始办理的早但完成的晚. 题解:我们可以用优先队列来模拟办理, ...

  8. 牛客编程巅峰赛S1第5场 - 青铜&amp&semi;白银 B&period;完全平方数的尾巴 &lpar;暴力&rpar;

    题意:有一个数\(x\),判断其是否能有某个完全平方数$mod$1000得到. 题解:直接写个for判断一下就好了,因为对1000取模,所以枚举到1000即可. 代码: class Solution ...

  9. 牛客编程巅峰赛S1第5场 - 青铜&amp&semi;白银 A&period;凯撒密码&lpar;字符串&rpar;

    题意:给你一个加密的字符串,以及偏移量,求对应的明文. 题解:根据样例,不难看出模板串是:\(0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopq ...

随机推荐

  1. 在SQL Server中将数据导出为XML和Json

        有时候需要一次性将SQL Server中的数据导出给其他部门的也许进行关联或分析,这种需求对于SSIS来说当然是非常简单,但很多时候仅仅需要一次性导出这些数据而建立一个SSIS包就显得小题大做 ...

  2. Windows Store App 过渡动画

    Windows Store App 过渡动画     在开发Windows应用商店应用程序时,如果希望界面元素进入或者离开屏幕时显得自然和流畅,可以为其添加过渡动画.过渡动画能够及时地提示用户屏幕所发 ...

  3. Linux中文件描述符fd和文件指针flip的理解

    转自:http://www.cnblogs.com/Jezze/archive/2011/12/23/2299861.html 简单归纳:fd只是一个整数,在open时产生.起到一个索引的作用,进程通 ...

  4. file的getPath getAbsolutePath和getCanonicalPath的不同

    file的这几个取得path的方法各有不同,下边说说详细的区别 概念上的区别:(内容来自jdk,个人感觉这个描述信息,只能让明白的人明白,不明白的人看起来还是有点难度(特别试中文版,英文版稍好些)所以 ...

  5. js一些算法实现

    1.约瑟夫环实现 //附有调试 function joseph(n,p){ var arr=[]; for(var i=0;i<n;i++){ arr.push(i); } debugger; ...

  6. 4069&colon; &lbrack;Apio2015&rsqb;巴厘岛的雕塑

    Description 印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道. 在这条主干道上一共有 N 座雕塑,为方便起见,我们把这些雕塑从 1 到 N 连续地进行标号,其中第 i 座雕塑的年龄 ...

  7. C语言的printf输出格式控制

    C语言的printf输出格式控制 printf大家都耳熟能详,但是能真正将其用法弄透的估计很少见. 转一篇,改天整理. 1．转换说明符 %a(%A)     浮点数.十六进制数字和p-(P-)记数法( ...

  8. 复习-C语言内嵌汇编-初级&lpar;2&rpar;

    汇编取出内存中的值 # include <stdio.h> int main() { ; ; int *p = &i; //ret = *p; __asm__( "ldr ...

  9. cocos2dx3&period;5 HTC One X 某些UI白屏或使用ClippingNode造成部分手机白屏

    public Cocos2dxGLSurfaceView onCreateView() { Cocos2dxGLSurfaceView glSurfaceView = new Cocos2dxGLSu ...

  10. &lbrack;标准性文档&rsqb;WEB应用安全验证标准

    这是根据OWASP ASVS翻译过来的,可作为WEB应用开发的验收标准(未包含具体细节),值得注意的是,验收标准并非越严格越好,应根据企业自身的业务需求判定. WEB应用安全验证标准 安全验证等级的定 ...