#481. [CSP-S 2026] 地铁
[CSP-S 2026] 地铁
地铁(subway)
CSP-S 2026 第二轮 · T2(赛题题意整理,测试数据为自制)
题目描述
一座城市有 个地铁站和 条地铁线路。第 个站的地铁口到站厅步行需要 的时间;第 条线路经过若干站,第 个经过的站是 ,从该站站厅到该线路站台步行需 的时间。各段通道反向步行耗时相同。
在同一条线路上坐车不计步行时间。要从一条线路换乘到另一条线路,必须先从前一条线路站台走到该站站厅,再进入后一条线路站台。中途换乘不需要走出地铁口,也不计中途站点的 。每个地铁站最多有 条线路经过,全部地铁站彼此可达。
给定 次出行,从 站地铁口出发,抵达 站地铁口。求每次出行的最小总步行时间。
输入格式
第一行五个整数 ,其中 是测试点编号,仅用于标识,不影响答案。
第二行 个正整数 。
随后 行,第 行先给出 ,再依次给出 对整数 ,表示第 条线路经过的站点及其站台通道耗时。同一线路不重复经过同一个站。
最后 行,每行两个整数 (保证 )。
输出格式
输出 行,每行一个非负整数,表示对应出行的最小总步行时间。
输入输出样例 #1
0 2 5 20 2
4 1 9 2 5
3 1 5 2 7 4 6
3 2 3 3 4 5 7
1 3
1 2
32
17
输入输出样例 #2
0 3 7 20 2
8 3 6 1 7 2 9
3 1 4 2 5 5 100
3 2 6 3 1 7 2
4 3 2 5 100 4 6 6 7
1 6
2 3
35
16
数据范围与说明
,,,。
,;所有地铁站彼此可达且每站经过的线路数不超过 。测试点编号 。
注意: Hydro 使用标准输入输出;测试数据自行生成,并非 CCF 官方测试数据。