比赛场次 | 611 |
---|---|
比赛名称 | 2024暑期C班集训1 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2024-07-01 08:15:00 |
结束时间 | 2024-07-01 12:00:00 |
开放分组 | 全部用户 |
注释介绍 | https://www.luogu.com.cn/paste/0jqk2xtz |
题目名称 | 熙熙攘攘、我们的城市 |
---|---|
输入输出 | Wrong_world.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 512 MiB |
测试点数 | 20 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
darkMoon | AAAAAAAAEAAEEATTTTEE |
8.239 s | 104.92 MiB | 55 |
AeeE5x | AAAAAAAATTTETTETTTTT |
11.745 s | 103.64 MiB | 40 |
┭┮﹏┭┮ | AAAAWWAWWWWWWWWWWWAA |
1.036 s | 88.70 MiB | 35 |
liuyiche | AAAATTATTTTTTTTTTTTT |
15.196 s | 74.40 MiB | 25 |
Untitled | AAAWWWAWWWWWWWWWWWWW |
2.065 s | 24.04 MiB | 20 |
wzh0425 | RRRRRRRRRRRRRRRRRRRR |
0.014 s | 9.59 MiB | 0 |
健康铀 | RRREEEEEEEEEEEEEEEEE |
3.615 s | 4.91 MiB | 0 |
Nina 又坐过站了。在终点站川崎下车后,她决定把川崎的铁路研究一遍。
川崎有 $n$ 个车站,以及 $m$ 条铁路,每条铁路都是单向运行的,第 $i$ 条铁路依次经过 $v_{i,1},v_{i,2},\dots,v_{i,l_i+1}$ 号车站并停靠,其中 $v_{i,j} \to v_{i,j+1}$ 的铁路长度是 $t_{i,j}$。
如果多条铁路经过 $u$ 号车站,那么 Nina 可以在 $u$ 号车站换乘其他铁路。(每条铁路都可以在停靠点任意上车/下车)
你需要帮 Nina 找到一条从 $1$ 号车站到 $n$ 号车站的路径,这条路径需要满足其总长度最小,并且在此条件上路径上相邻两个换乘点间火车上距离的平方和最大。
注:起点和终点都是换乘点,题目保证有解。
第一行两个整数 $n,m$ 表示有 $n$ 个车站,$m$ 条铁路。
接下来 $m$ 行,每行先是一个整数 $l_i$ 表示铁路长度,接下来 $2l_i+1$ 个整数形如 $v_{i,1},t_{i,1},v_{i,2},\dots,v_{i,l_i},t_{i,l_i},v_{i,l_i+1}$,含义如题所示。
一行两个整数,第一个数表示最短路径长度,第二个数表示平方和最大值。
2 1 1 1 3 2
3 9
5 2 4 1 3 2 3 3 5 5 10 4 3 4 2 2 1 3 4 1
9 35
从 $1$ 号车站乘坐 $1$ 号线直达 $5$ 号车站并非最佳方案(无法达到最短时间)。
最佳方案为:
·从 $1$ 号车站乘坐 $1$ 号线到 $2$ 号车站;
·换乘 $2$ 号线,坐到 $3$ 号车站;
·再换乘 $1$ 号线,坐到 $5$ 号车站。
此时,平方和为 $3^2 + 1^2 + 5^2 = 35$。
5 2 3 1 1 2 2 3 3 4 3 2 2 3 3 4 4 5
10 82
对于 $100\%$ 的数据:$1 \le n,m \le 10^6, 1 \le v_{i,j} \le n, 1 \le t_{i,j} \le 1000$,设 $sum=\sum l_i$。
·$Subtask1(10pts): n\le 10,sum\le 20$。
·$Subtask2(10pts): n,sum\le 10^3$。
·$Subtask3(20pts): n\le 10^3,sum\le 10^5$。
·$Subtask4(60pts): sum\le 10^6$。
「ROI 2017 Day 1」前往大都会。