AT_abc414_g.[ABC414G] AtCoder Express 4

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

AtCoder 王国有一条东西向的铁路线，这条线路上有 $1,2,\ldots,N$ 号车站。第 $i$ 号车站（ $1\leq i\leq N$ ）位于坐标 $x_i$ 上（ $x_1 < x_2 < \ldots < x_N$ ）。

在这条线路上，AtCoder Express 公司运营着 $M$ 种特急列车。

第 $i$ 种特急列车的运行方式如下：

可以在第 $l_i,l_i+1,\ldots,r_i$ 号车站中的任意一个上车。
可以在第 $L_i,L_i+1,\ldots,R_i$ 号车站中的任意一个下车。此时，列车的行驶方向仅为东西某一方向，满足 $r_i < L_i$ 或 $R_i < l_i$ 。
票价为初乘票价 $c_i$ ，再加上上车站到下车站的距离。具体来说，从第 $s$ 号车站（ $l_i\leq s\leq r_i$ ）乘车到第 $t$ 号车站（ $L_i\leq t\leq R_i$ ）时，票价为 $c_i+|x_s-x_t|$ 。

你现在在第 $1$ 号车站。对于每个 $k$ （ $2\leq k\leq N$ ），请判断是否可以通过换乘特急列车从第 $1$ 号车站到达第 $k$ 号车站。如果可以到达，请求出所需总票价的最小值。

输入按以下格式从标准输入给出。

$N$ $M$
$x_1$ $x_2$ $\ldots$ $x_N$
$l_1$ $r_1$ $L_1$ $R_1$ $c_1$
$l_2$ $r_2$ $L_2$ $R_2$ $c_2$
$\vdots$
$l_M$ $r_M$ $L_M$ $R_M$ $c_M$

请按以下格式输出答案。

$\mathrm{ans}_2$ $\mathrm{ans}_3$ $\ldots$ $\mathrm{ans}_N$

$\mathrm{ans}_i$ 表示 $k=i$ 时的答案。如果可以从第 $1$ 号车站到达第 $i$ 号车站，则输出所需总票价的最小值；否则输出 $-1$ 。

输入#1

6 3
0 20 50 90 110 150
1 2 5 6 100
1 1 2 3 10000
6 6 1 2 30

输出#1

410 10050 -1 210 250

输入#2

10 5
4427 6839 17992 39701 46954 76602 81804 91814 95651 95895
3 4 10 10 60978
1 1 4 4 30037
9 10 7 8 66643
4 4 1 2 50872
8 10 3 7 23949

输出#2

149045 284335 65311 255373 225725 220523 253207 -1 182483

可以如下到达第 $2$ 号车站：

此时总票价为 $410$ ，且这是最小值。无法到达第 $4$ 号车站。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?