#PQJ29x5220. QOJ 29_5220
QOJ 29_5220
2016 年全国青少年信息学奥林匹克浙江省队选拔赛第一试
旅行者
旅行者
【问题描述】
小Y 来到了一个新的城市旅行。她发现了这个城市的布局是网格状的,也
就是有 𝑛𝑛 条从东到西的道路和 𝑚𝑚 条从南到北的道路,这些道路两两相交形成
𝑛𝑛 × 𝑚𝑚 个路口 (𝑖𝑖, 𝑗𝑗) (1 ≤𝑖𝑖≤𝑛𝑛, 1 ≤𝑗𝑗≤𝑚𝑚) 。
她发现不同的道路路况不同,所以通过不同的路口需要不同的时间。通过调
查发现,从路口 (𝑖𝑖, 𝑗𝑗) 到路口 (𝑖𝑖, 𝑗𝑗+ 1) 需要时间 𝑟𝑟𝑖𝑖,𝑗𝑗,从路口 (𝑖𝑖, 𝑗𝑗) 到路口 (𝑖𝑖+ 1, 𝑗𝑗)
需要时间 𝑐𝑐𝑖𝑖,𝑗𝑗。注意这里的道路是双向的,也就是从路口 (𝑖𝑖, 𝑗𝑗+ 1) 到路口 (𝑖𝑖, 𝑗𝑗) 需
要时间同样是 𝑟𝑟𝑖𝑖,𝑗𝑗。
小Y 有 𝑞𝑞 个询问,她想知道从路口 (𝑥𝑥1, 𝑦𝑦1) 到路口 (𝑥𝑥2, 𝑦𝑦2) 最少需要花多少
时间。
【输入格式】
输入文件tourist.in 第一行包含 2 个正整数 𝑛𝑛, 𝑚𝑚 ,表示城市的大小。
接下来 𝑛𝑛 行,每行包含 𝑚𝑚−1 个整数,第 𝑖𝑖 行第 𝑗𝑗 个正整数表示从一个路口
到另一个路口的时间 𝑟𝑟𝑖𝑖,𝑗𝑗 。
接下来 𝑛𝑛−1 行,每行包含 𝑚𝑚 个整数,第 𝑖𝑖 行第 𝑗𝑗 个正整数表示从一个路口
到另一个路口的时间 𝑐𝑐𝑖𝑖,𝑗𝑗 。
接下来一行,包含 1 个正整数 𝑞𝑞 ,表示小Y 的询问个数。
接下来 𝑞𝑞 行,每行包含 4 个正整数 𝑥𝑥1, 𝑦𝑦1, 𝑥𝑥2, 𝑦𝑦2,表示两个路口的位置。
【输出格式】
输出文件为tourist.out。
输出共 𝑞𝑞 行,每行包含一个整数表示从一个路口到另一个路口最少需要花的
时间。
【样例输入1】
2 2
2
3
6 4
2
1 1 2 2
1 2 2 1
2016 年全国青少年信息学奥林匹克浙江省队选拔赛第一试 旅行者 【样例输出1】 6 7 【样例输入2】 2 3 558 163 102 2000 461 1732 561 2 2 1 2 3 1 2 2 2 【样例输出2】 1743 1121 【样例输入输出3】 见选手目录下的tourist/tourist.in 与tourist/tourist.ans。 【数据规模和约定】 对于所有的测试数据,保证相邻路口之间的时间不超过 104 ,即 1 ≤ 𝑟𝑟𝑖𝑖,𝑗𝑗, 𝑐𝑐𝑖𝑖,𝑗𝑗≤104 。 各测试点满足以下约定: 测试点 𝑛𝑛∗𝑚𝑚 q 约定 1 ≤103 ≤103 无 2 3 ≤2 × 104 ≤105 min (𝑛𝑛, 𝑚𝑚) ≤4 4 5 6 无 7 8 9 10