本题关联比赛
2024暑期C班集训1

关于熙熙攘攘、我们的城市的近10条评论(全部评论)
趁讲之前口胡一个，每个节点记录一个值 dis_i 和 vector 数组 v_i，表示 1 到 i 的最短距离，和通过某一条铁轨，一直不换乘的情况下，走的最长距离，然后显然我们只需要考虑通过某些铁轨能到达 i 且保持最小距离的，同时也只能通过这些铁轨转移，然后转移就按照记录的值和数组简单的转移，基于 dij。感觉好简陋的思路，但是感觉好对啊：） darkMoon 2024-07-01 15:38 1楼

3987. 熙熙攘攘、我们的城市

★★★ 输入文件：Wrong_world.in 输出文件：Wrong_world.out 简单对比
时间限制：1 s 内存限制：512 MiB

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」前往大都会。