{"problem":{"name":"[ROI 2017] 前往大都会 (Day 1)","description":{"content":"ROI 国有 $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$ 号城市，那么你可以在 $u$ 号城市换乘其他铁路。（每条铁路都可以在停靠点任意上车/","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10652"},"statements":[{"statement_type":"Markdown","content":"ROI 国有 $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}$。\n\n如果多条铁路经过 $u$ 号城市，那么你可以在 $u$ 号城市换乘其他铁路。（每条铁路都可以在停靠点任意上车/下车）\n\n你需要找到一条从 $1$ 号城市到 $n$ 号城市的路径，这条路径需要满足其总长度最小，并且在此条件上路径上相邻两个**换乘点**间**火车上**距离的平方和最大。\n\n注：起点和终点都是换乘点，题目保证有解。\n\n## Input\n\n第一行两个整数 $n,m$ 表示有 $n$ 个城市，$m$ 条铁路。\n\n接下来 $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}$，含义如题所示。保证其中不包含重复的城市。\n\n## Output\n\n一行两个整数，第一个数表示最短路径长度，第二个数表示平方和最大值。\n\n[samples]\n\n## Note\n\n#### 【样例解释】\n\n对于样例组 #2：\n\n从 $1$ 号城市乘坐 $1$ 号线直达 $5$ 号城市并非最佳方案（无法达到最短时间）。最佳方案：\n\n>从 $1$ 号城市乘坐 $1$ 号线到 $2$ 号城市；\n>\n> 换乘 $2$ 号线，坐到 $3$ 号城市；\n>\n> 再换乘 $1$ 号线，坐到 $5$ 号城市。\n\n此时，平方和为 $3^2 + 1^2 + 5^2 = 35$。\n\n对于样例组 #3：\n\n无论是在中途哪一站转 $2$ 号线，结果都一样。平方和为 $1^2+9^2=82$。\n\n#### 【数据范围】\n\n注：本题只放部分数据，完整数据请左转 [LOJ P2769](https://loj.ac/p/2769) 评测。\n\n对于所有数据：$1 \\le m \\le 10^6$，$1 \\le v_{i,j} \\le n$，$1 \\le t_{i,j} \\le 1000$，设 $sum=\\sum l_i$。\n\n| 子任务编号 | 分值 | $1 \\le n \\le $ | $1 \\le sum \\le $ |特殊性质|\n| :----------: | :----------: | :----------: | :----------: | :----------: |\n| $1$ | $10$ | $10$ | $20$ |$l_i=1$|\n| $2$ | $10$ | $10^3$ | $10^3$ |$l_i=1$|\n| $3$ | $17$ | $10^3$ | $10^3$ |无|\n| $4$ | $17$ | $10^3$ | $10^5$ |无|\n| $5$ | $19$ | $10^4$ | $2 \\times 10^5$ |无|\n| $6$ | $19$ | $2 \\times 10^5$ | $2 \\times 10^5$ |无|\n| $7$ | $8$ | $10^6$ | $10^6$ |无|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10652","tags":["动态规划 DP","2017","O2优化","斜率优化","最短路","ROI（俄罗斯）"],"sample_group":[["2 1\n1 1 3 2","3 9"],["5 2\n4 1 3 2 3 3 5 5 10 4\n3 4 2 2 1 3 4 1","9 35"],["5 2\n3 1 1 2 2 3 3 4\n3 2 2 3 3 4 4 5","10 82"]],"created_at":"2026-03-03 11:09:25"}}