#P18845. [Croatian CPC2022] Glomazna Gužva
[Croatian CPC2022] Glomazna Gužva
Glomazna Gužva
题目描述
把一座城市看作无限的矩形街道网格。每个路口都位于整数坐标处,相邻路口之间的一段街道称为一个街区。通常,经过一个街区需要 分钟。
城市中正在举行一些外交访问活动,每次活动都会使一个矩形区域发生交通拥堵。严格位于该矩形内部的街道受到拥堵影响,经过其中一个街区需要的时间变为该区域给定的 分钟。沿矩形边界行驶的街道不受该区域影响。穿过内部的街区即使端点在边界上,也按该区域的时间计费。
不同拥堵矩形之间既不相交,也不接触。
给定起点 、终点 和所有拥堵区域,求从 行驶到 的最短时间。只能沿街道在相邻整数坐标路口之间移动。

输入格式
第一行包含四个整数 ,表示起点和终点的坐标。
第二行包含一个整数 ,表示拥堵矩形数量。
接下来 行,每行包含五个整数 。前四个数分别表示矩形左下角和右上角的坐标,最后一个数表示在该矩形内部经过一个街区所需的分钟数。
输出格式
输出一个整数,表示从 到 的最短时间,单位为分钟。
数据范围与保证
- ;
- ;
- ,;
- ;
- 任意两个拥堵矩形既不相交,也不接触;
- 起点与终点不同,且均不在任何拥堵矩形内部或边界上。
样例 1
输入
1 6 15 3
4
2 1 3 7 44
5 2 10 4 33
8 5 11 9 22
12 1 14 8 11
输出
192
样例 2
输入
1 6 15 3
4
2 1 3 7 11
5 2 10 4 22
8 5 11 9 33
12 1 14 8 44
输出
210
样例 1 解释
样例 1 对应题目描述中的示意图。图中的黑色路线给出一种最优走法。