CCF全国青少年信息学奥林匹克竞赛（NOIP2018）第一试（图片版，无答案）

全国青少年信息学奥林匹克竞赛
CCF
NOI
2018
第一试
时间:2018年7月18日08:00~13.00
题目名称
归程
冒泡排序
你的名字
题目类型
传统型
体刑
传统型
目录
return
Inverse
name
可执行文件名
return
Inverse
name
输入文件名
return.
in
Inverse。in
name.
ln
输出文件名
return。out
inverse
out
name
out
每个测试点时限4.0秒
10秒
4.0
秒
内存限制
512MB
512MB
1
GB
测试点/包数目
20
25
测试点是否等分是
是
是
提交源程序文件名
对于C++语言
return.
cpp
Inverse.
cpp
name.
cpp
对于C语言
return.
C
Inverse.
C
name.
c
对于
Pascal话言
return.
pas
inverse
pas
name.
pas
编译选项
对于C++语言
-02.-1m
对于C语言
2-1m
对于Pl话言
02
注意事项
1、提交的源文件必须存放在已建立好的下发样例的文件夹中(该文件夹与试题同名)
2、文件名(包括程序名和输入输出文件名)必须使用英文小写
3、结果比较方式为忽略行末空格、文末回车后的全文比较
4、C/O++中函数
main()的返回值类型必须是int,值为0。
对于因未遵守以上规则对成绩造成的影响,相关申诉不予受理。
全国青少年信息学奥林匹克竞赛
第一试归程(
return)
归程(
return)
【题目背景】
本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。
魔力之都可以抽象成一个n个节点、m条边的无向连通图(节点的编号从1至n)
我们依次用l,a描述一条边的长度、海拔。
作为季风气候的代表城市,魔力之都时常有雨水相伴,因此道路积水总是不可避免
的。由于整个城市的排水系统连通,因此有积水的边一定是海拔相对最低的一些边
我们用水位线来描述降雨的程度,它的意义是:所有海拔不超过水位线的边都是有
积水的。
题目描述】
Yazid是一名来自魔力之都的Oler,刚参加完ION2018的他将踏上归程,回到他
温暖的家
Yazid的家恰好在魔力之都的1号节点。对于接下来Q天,每一天Yazd都会告
诉你他的出发点v,以及当天的水位线p
每一天,
Yazid在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。
Yazd可以在任意节点下车,这样接下来他就可以步行经过有积水的边。但车会被留在
他下车的节点并不会再被使用
●需要特殊说明的是,第二天车会被重置,这意味着:
车会在新的出发点被准备好
Yazd不能利用之前在某处停放的车。
Yazd非常讨厌在雨天步行,因此他希望在完成回家这一目标的同时,最小化他步
行经过的边的总长度。请你帮助
Yazid进行计算。
本题的部分测试点将强制在线,具体细节请见【输入格式】和【子任务】
【输入格式】
从文件
return
i7中读入数据
单个测试点中包含多组数据。输入的第一行为一个非负整数T,表示数据的组数
接下来依次描述每组数据,对于每组数据:
第一行2个非负整数n,m,分别表示节点数、边数
●接下来m行,每行4个正整数v,y,l,a,描述一条连接节点u,v的、长度为l海
拔为a的边
在这里,我们保证1≤L,v≤n。
第2页共12页