#P18845. [Croatian CPC2022] Glomazna Gužva

[Croatian CPC2022] Glomazna Gužva

Glomazna Gužva

题目描述

把一座城市看作无限的矩形街道网格。每个路口都位于整数坐标处,相邻路口之间的一段街道称为一个街区。通常,经过一个街区需要 1010 分钟。

城市中正在举行一些外交访问活动,每次活动都会使一个矩形区域发生交通拥堵。严格位于该矩形内部的街道受到拥堵影响,经过其中一个街区需要的时间变为该区域给定的 tit_i 分钟。沿矩形边界行驶的街道不受该区域影响。穿过内部的街区即使端点在边界上,也按该区域的时间计费。

不同拥堵矩形之间既不相交,也不接触。

给定起点 AA、终点 BB 和所有拥堵区域,求从 AA 行驶到 BB 的最短时间。只能沿街道在相邻整数坐标路口之间移动。

城市道路与拥堵区域示意图

输入格式

第一行包含四个整数 xA,yA,xB,yBx_A,y_A,x_B,y_B,表示起点和终点的坐标。

第二行包含一个整数 nn,表示拥堵矩形数量。

接下来 nn 行,每行包含五个整数 x1,i,y1,i,x2,i,y2,i,tix_{1,i},y_{1,i},x_{2,i},y_{2,i},t_i。前四个数分别表示矩形左下角和右上角的坐标,最后一个数表示在该矩形内部经过一个街区所需的分钟数。

输出格式

输出一个整数,表示从 AA 到 BB 的最短时间,单位为分钟。

数据范围与保证

  • ∣xA∣,∣yA∣,∣xB∣,∣yB∣≤108|x_A|,|y_A|,|x_B|,|y_B|\le10^8;
  • 0≤n≤10000\le n\le1000;
  • x1,i<x2,ix_{1,i}<x_{2,i},y1,i<y2,iy_{1,i}<y_{2,i};
  • 10<ti≤10810<t_i\le10^8;
  • 任意两个拥堵矩形既不相交,也不接触;
  • 起点与终点不同,且均不在任何拥堵矩形内部或边界上。

样例 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 对应题目描述中的示意图。图中的黑色路线给出一种最优走法。