牛客 2018年长沙理工大学第十三届程序设计竞赛 E-小木乃伊到我家

本文主要是介绍牛客 2018年长沙理工大学第十三届程序设计竞赛 E-小木乃伊到我家,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

链接:https://www.nowcoder.com/acm/contest/96/E
来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld

题目描述

AA的欧尼酱qwb是个考古学家,有一天qwb发现了只白白圆圆小小的木乃伊,它是个爱哭鬼却很努力。qwb想把这么可爱的小木乃伊送给
AA,于是便找上了快递姐姐,这下可让快递姐姐犯愁了,因为去往AA家的路实在太难走了(甚至有可能没有路能走到AA家),快递姐姐
找上聪明的ACMer,想请你帮忙找出最快到达AA家的路,你行吗?

输入描述:

第一行输入两个整数n和m(2<=n<=m<=200000),分别表示有n座城市和m条路,城市编号为1~n(快递姐姐所在城市为1,AA所在城市为n)。
接下来m行,每行输入3个整数u,v,w(u,v<=n,w<=100000),分别表示城市u和城市v之间有一条长为w的路。

输出描述:

输出结果占一行,输出快递姐姐到达AA家最短需要走多远的路,如果没有路能走到AA家,则输出“qwb baka”(不用输出双引号)。
示例1

输入

4 4
1 2 1
2 3 2
3 4 3
2 3 1

输出

5

分析:裸的最短路,最后判断一下有没有解即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 999999999
using namespace std;
int N,M,S,T;
struct Node{int s,t,c;
}edge[400050];
int next1[400050],head[400050];
int vis[400050],d[400050];void spfa()
{for(int i=0;i<=N;i++) {d[i]=INF;vis[i]=0;} d[S]=0;vis[S]=1;queue<int> q;q.push(S);while(!q.empty()){int v=q.front();vis[v]=0;q.pop();int k=head[v];while(k!=-1){int i=edge[k].t;if(d[i]>d[v]+edge[k].c){d[i]=d[v]+edge[k].c;if(!vis[i]){vis[i]=1;q.push(i);}}k=next1[k];}}
}int main()
{scanf("%d%d",&N,&M);S=1,T=N;memset(head,-1,sizeof(head));M*=2;for(int i=0;i<M;i++){scanf("%d%d%d",&edge[i].s,&edge[i].t,&edge[i].c);next1[i]=head[edge[i].s];head[edge[i].s]=i;i++;edge[i].s=edge[i-1].t;edge[i].t=edge[i-1].s;edge[i].c=edge[i-1].c;next1[i]=head[edge[i].s];head[edge[i].s]=i;}spfa();if(d[T]<INF)printf("%d\n",d[T]);else printf("qwb baka\n");return 0;
}
View Code

 








转载于:https://www.cnblogs.com/ACRykl/p/8834069.html

这篇关于牛客 2018年长沙理工大学第十三届程序设计竞赛 E-小木乃伊到我家的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/392013

相关文章

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

C语言程序设计(数据类型、运算符与表达式)

一、C的数据类型 C语言提供的数据类型: 二、常量和变量 2.1常量和符号常量 在程序运行过程中,其值不能被改变的量称为常量。 常量区分为不同的类型: 程序中用#define(预处理器指令)命令行定义变量将代表常量,用一个标识符代表一个常量,称为符合常量。 2.2变量 变量代表内存中具有特定属性的一个存储单元,用来存放数据,在程序运行期间,这些值是可以 改变的。 变

C语言程序设计(选择结构程序设计)

一、关系运算符和关系表达式 1.1关系运算符及其优先次序 ①<(小于) ②<=(小于或等于) ③>(大于) ④>=(大于或等于 ) ⑤==(等于) ⑥!=(不等于) 说明: 前4个优先级相同,后2个优先级相同,关系运算符的优先级低于算术运算符,关系运算符的优先级高于赋值运算符 1.2关系表达式 用关系运算符将两个表达式(可以是算术表达式或关系表达式,逻辑表达式,赋值表达式,字符

2024年AMC10美国数学竞赛倒计时两个月:吃透1250道真题和知识点(持续)

根据通知,2024年AMC10美国数学竞赛的报名还有两周,正式比赛还有两个月就要开始了。计划参赛的孩子们要记好时间,认真备考,最后冲刺再提高成绩。 那么如何备考2024年AMC10美国数学竞赛呢?做真题,吃透真题和背后的知识点是备考AMC8、AMC10有效的方法之一。通过做真题,可以帮助孩子找到真实竞赛的感觉,而且更加贴近比赛的内容,可以通过真题查漏补缺,更有针对性的补齐知识的短板。

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

智能工厂程序设计 之1 智能工厂都本俱的方面(Facet,Aspect和Respect)即智能依赖的基底Substrate 之1

Q1、昨天分别给出了三个智能工厂的 “面face”(里面inter-face,外面outer-face和表面surface) 以及每个“面face” 各自使用的“方”(StringProcessor,CaseFilter和ModeAdapter)  。今天我们将继续说说三个智能工厂的“方面” 。在展开之前先看一下三个单词:面向facing,取向oriented,朝向toword。理解这三个词 和

2024 年高教社杯全国大学生数学建模竞赛题目——2024 年高教社杯全国大学生数学建模竞赛题目的求解

2024 年高教社杯全国大学生数学建模竞赛题目 (请先阅读“ 全国大学生数学建模竞赛论文格式规范 ”) 2024 年高教社杯全国大学生数学建模竞赛题目 随着城市化进程的加快、机动车的快速普及, 以及人们活动范围的不断扩大,城市道 路交通拥堵问题日渐严重,即使在一些非中心城市,道路交通拥堵问题也成为影响地方经 济发展和百姓幸福感的一个“痛点”,是相关部门的棘手难题之一。 考虑一个拥有知名景区

2024 年高教社杯全国大学生数学建模竞赛 C 题 农作物的种植策略 参考论文 无水印

持续更新中,2024年数学建模比赛思路代码论文都会发布到专栏内,只需订阅一次!  完整论文+代码+数据结果链接在文末!  订阅后可查看参考论文文件 第一问 1.1 问题重述 这个问题围绕的是华北山区的某乡村,在有限的耕地条件下,如何制定最优的农作物种植策略。乡村有 34 块露天耕地和 20 个大棚,种植条件包括粮食作物、蔬菜、水稻和食用菌。除了要考虑地块的面积、种植季节等,还要确保

2018秋招C/C++面试题总结

博主从8月中旬开始大大小小面试了十几家公司,至今也许是告一段落吧,希望后面会有好结果,因此总结记录一些C/C++方向常见的问题。和大家一起学习! 参考了互联网的各种资源,自己尝试归类整理,谢谢~ 一、C和C++的区别是什么? C是面向过程的语言,C++是在C语言的基础上开发的一种面向对象编程语言,应用广泛。 C中函数不能进行重载,C++函数可以重载 C++在C的基础上增添类,C是一个结构