题面下载

样例下载

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

在浩瀚的“曙梦星海”中，领航员小木负责规划“曙梦号”飞船在各大星际空间站之间的航行路线。为了节省燃料，小木打算利用古老文明遗留在星海中的“星轨跃迁门”。

题目描述

星海的一段主航道可以视作一个无限长的一维数轴。航道上分布着 $n$ 个空间站，其坐标分别为整点 $a_1,\cdots,a_n$（不同的空间站可能位于同一坐标）。

航道上存在 $m$ 个星轨跃迁门，每个跃迁门可以用一个四元组 $(l,r,c,t)$ 来表示：这意味着飞船在坐标区间 $[l,r]$ 上的任意一点，都可以单向跃迁至坐标 $t$ 处，且该次跃迁需要消耗 $c$ 个时间单位。

此外，“曙梦号”在航道上也可以依靠常规动力进行双向游走，每移动 $1$ 个长度单位花费 $1$ 个时间单位。

小木需要计算出：在航道中，从空间站 $a_i$ 出发前往空间站 $a_j$ 的最短耗时是多少（要求 $i<j$）。

输入格式

从标准输入读入数据。

第一行输入一个整数 $n$。

接下来一行 $n$ 个整数 $a_1,\cdots,a_n$，用空格分隔。

接下来一行一个整数 $m$。

接下来 $m$ 行，每行四个整数 $l,r,c,t$，代表每个跃迁门的具体参数。

输出格式

输出到标准输出。

输出 $n-1$ 行，第 $i$ 行输出 $n-i$ 个整数，依次分别表示从空间站 $a_i$ 到 $a_{i+1},\cdots,a_n$ 的最短耗时。

3
1 5 10
0

4 9
5

样例 1 解释

在本段航道中，存在 $3$ 个空间站，坐标分别为 $1, 5, 10$。由于不存在星轨跃迁门（$m=0$），领航员小木只能安排“曙梦号”依靠常规动力在各空间站之间直接飞行。 具体航行规划如下：

• 从空间站 $1$ 出发：
  • 前往空间站 $2$（坐标 $5$），直接飞行的距离为 $|1-5|=4$，耗时为 $4$。
  • 前往空间站 $3$（坐标 $10$），直接飞行的距离为 $|1-10|=9$，耗时为 $9$。
• 从空间站 $2$ 出发：
  • 前往空间站 $3$（坐标 $10$），直接飞行的距离为 $|5-10|=5$，耗时为 $5$。

4
1 5 10 20
1
2 3 1 18

4 9 4
5 5
10

样例 2 解释

在本段航道中，存在 $4$ 个空间站，且遗留了 $1$ 座星轨跃迁门。该跃迁门的触发区间在 $[2, 3]$，单次跃迁消耗 $1$ 个时间单位，落地坐标为 $18$。 “曙梦号”在部分遥远的航线上可以通过跃迁门大幅节省时间，具体航行规划如下：

• 从空间站 $1$（坐标 $1$）出发：

  • 去往空间站 $2$（坐标 $5$）和空间站 $3$（坐标 $10$）时，依靠常规动力直接飞行的耗时（分别为 $4$ 和 $9$）均优于绕道跃迁门的耗时，故最短耗时分别为 $4, 9$。
  • 去往空间站 $4$（坐标 $20$）时，如果直接飞行需要耗时 $19$。小木的最优规划是：先依靠常规动力航行至坐标 $2$ 处（耗时 $1$），触发星轨跃迁门（耗时 $1$）瞬间抵达坐标 $18$ 处，最后再依靠常规动力航行至坐标 $20$（耗时 $2$）。总耗时仅为 $1+1+2=4$。

• 从空间站 $2$（坐标 $5$）出发：

  • 去往空间站 $3$（坐标 $10$），直接飞行耗时 $5$。
  • 去往空间站 $4$（坐标 $20$），直接飞行耗时 $15$。最优规划为：反向航行至坐标 $3$ 处进入跃迁门（耗时 $2$），跃迁至坐标 $18$（耗时 $1$），再航行至终点（耗时 $2$），总耗时为 $2+1+2=5$。

• 从空间站 $3$（坐标 $10$）出发：

  • 去往空间站 $4$（坐标 $20$），直接飞行的耗时为 $10$；若使用跃迁门，需先反向飞到坐标 $3$（耗时 $7$），跃迁（耗时 $1$）到 $18$ 后再飞往 $20$（耗时 $2$），总耗时也是 $10$。因此最短耗时为 $10$。

子任务

对于所有数据：

• $2\le n\le 100$；
• $0\le |a_i|,|l|,|r|,|t|,c\le 10^9$；
• $l\le r$；
• $m\in\{0,1\}$

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。