@[spfa](/space/show?uid=17850) 洛谷群里面有
by chen_zhe @ 2018-07-18 08:38:55
[题目](http://labelray.top/wp-content/uploads/2018/07/day01.tar.gz)
by Labelray @ 2018-07-18 08:38:57
有没有人可以发一下题面
by 乌合之众 @ 2018-07-18 08:39:55
归程
【题目背景】
本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。
魔力之都可以抽象成一个 n 个节点、m 条边的无向连通图(节点的编号从1至n)。我们依次用 l, a 描述一条边的长度、海拔。
作为季风气候的代表城市,魔力之都时常有雨水相伴,因此道路积水总是不可避免的。由于整个城市的排水系统连通,因此有积水的边一定是海拔相对最低的一些边。
我们用水位线来描述降雨的程度,它的意义是:所有海拔不超过水位线的边都是有积水的。
具体详细试题描述见PDF链接文件,题目以PDF链接文件为准。
【题目描述】
Yazid 是一名来自魔力之都的 OIer,刚参加完 ION2018 的他将踏上归程,回到他温暖的家。
Yazid 的家恰好在魔力之都的 1 号节点。对于接下来 Q 天,每一天 Yazid 都会告诉你他的出发点 v ,以及当天的水位线 p。
每一天,Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车,这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。
需要特殊说明的是,第二天车会被重置,这意味着:
?车会在新的出发点被准备好。
?Yazid 不能利用之前在某处停放的车。
Yazid 非常讨厌在雨天步行,因此他希望在完成回家这一目标的同时,最小化他步行经过的边的总长度。请你帮助Yazid进行计算。
本题的部分测试点将强制在线,具体细节请见PDF链接文件。
【输入形式】
从文件 return.in 中读入数据。
单个测试点中包含多组数据。输入的第一行为一个非负整数 T ,表示数据的组数。接下来依次描述每组数据,对于每组数据:
?第一行 2 个非负整数 n, m,分别表示节点数、边数。
?接下来 m 行,每行 4 个正整数 u, v, l, a,描述一条连接节点 u, v 的、长度为 l、海拔为 a 的边。
?在这里,我们保证 1 ≤ u, v ≤ n。
?接下来一行 3 个非负数 Q, K, S ,其中 Q 表示总天数,K ∈ {0, 1} 是一个会在下面被用到的系数,S 表示的是可能的最高水位线。
?接下来 Q 行依次描述每天的状况。每行 2 个整数 v0 , p0 描述一天:
?这一天的出发节点为:v=(v0+K*lastans-1) mod n + 1。
?这一天的水位线为: p=(p0+K*lastans) mod (S+1)。
?其中 lastans 表示上一天的答案(最小步行总路程)。特别地,我们规定第 1天时 lastans = 0。
?在这里,我们保证 1 ≤ v0 ≤ n,0 ≤ p0 ≤ S 。
对于输入中的每一行,如果该行包含多个数,则用单个空格将它们隔开。
具体描述见PDF链接文件,题目以PDF链接文件为准。
【输出形式】
输出到文件 return.out 中。
依次输出各组数据的答案。对于每组数据:
?输出 Q 行每行一个整数,依次表示每天的最小步行总路程。
【输入样例1】
1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2
【输出样例1】
0
50
200
50
150
【样例2】
见下发数据中的return/return2.in与return/return2.ans。
【样例3】
见下发数据中的return/return3.in与return/return3.ans。
【样例4】
见下发数据中的return/return4.in与return/return4.ans。
【样例5】
见下发数据中的return/return5.in与return/return5.ans。
【时间限制】
4.0s
【空间限制】
512000KB
【上传文件】
上传c, cpp, pas语言源程序,文件名为return.c, return.cpp, return.pas。
by ChthollyTree @ 2018-07-18 08:40:08
首页卡死怎么办?
by owlAlice @ 2018-07-18 08:40:53
洛谷群是啥啊 求大佬们救救w
by hanyuwei @ 2018-07-18 08:42:24
感谢
by Chaigidel @ 2018-07-18 08:42:40
https://files.cnblogs.com/files/ztz11/day01.tar.gz
by ztz11 @ 2018-07-18 08:46:19
这个也许快一点(我们机房百度网盘被墙)
by ztz11 @ 2018-07-18 08:47:08
![luogu](https://cdn.luogu.com.cn/upload/pic/23973.png)
这样怎么办啊各位大佬
by owlAlice @ 2018-07-18 08:51:29