16054 - 机器人

时间限制 2 秒 内存限制 1024 MB

题目描述

NOI2025 正在绍兴举办，小 Y 为闭幕式表演制作了一个机器人并打算操控它从仓库走到礼堂。

绍兴的道路系统可以简化为 $n$ 个路口以及连接这些路口的 $m$ 条 单行道路，且每条道路有一定的长度。为了方便将道路系统录入机器人的芯片，小 Y 对每一个路口连接的所有道路进行了编号。具体而言，若有 $d$ 条道路以路口 $x$ 为起点，则这 $d$ 条道路会被小 Y 按照某种顺序编号为 $1 \sim d$ ，分别称作以 $x$ 为起点的第 $1 \sim d$ 条道路。

小 Y 的机器人内部有一个参数 $p$ 。给定参数 $p$ 的上限 $k$ 与修改费用 $v_1, v_2, \ldots, v_k-1, w_2, w_3, \ldots, w_k$ 。小 Y 将按照如下规则设置与修改机器人的参数：

初始时，小 Y 将参数 $p$ 设置为 $1$ 。
在 任意时刻，小 Y 可以远程控制机器人修改参数：
- 若 $p < k$ ，则小 Y 可以花费 $v_p$ 的费用将 $p$ 增加 $1$ ，即 $p \leftarrow p + 1$ ；
- 若 $p > 1$ ，则小 Y 可以花费 $w_p$ 的费用将 $p$ 减少 $1$ ，即 $p \leftarrow p - 1$ 。

初始时，小 Y 的机器人位于机器人仓库，即路口 $1$ 。当机器人位于路口 $x$ 时，记以路口 $x$ 为起点的第 $p$ 条道路的终点为 $y$ ，道路长度为 $z$ ，则小 Y 可以花费 $z$ 的费用操控机器人从 $x$ 走到 $y$ 。特别地，若以路口 $x$ 为起点的道路不足 $p$ 条，则小 Y 无法操控机器人走动。

小 Y 并不知道闭幕式表演所在的礼堂位于哪个路口，因此他需要对每个路口都做好准备。请你帮助他求出将机器人从仓库移动到每个路口所需费用的最小值。

输入

输出

输出一行 $n$ 个整数，其中第 $i$ （ $1 \leq i \leq n$ ）个数表示小 Y 将机器人从仓库移动到路口 $i$ 所需费用的最小值。特别地，若小 Y 无法将机器人从仓库移动到该路口，则输出 $-1$ 。

样例

样例 1

输入

0
5 6 3
2 4
1 1
3 2 5 3 1 4 2
1 3 2
2 1 2 4 1
0
0

输出

0 5 3 4 -1

提示

样例 1 解释

小 Y 可以按照以下方案将机器人分别从仓库移动到路口 $1 \sim 4$ ：

对于路口 $1$ ：小 Y 的机器人初始时即位于路口 $1$ ，因此所需费用为 $0$ 。
对于路口 $2$ ：小 Y 操控机器人沿以路口 $1$ 为起点的第 $1$ 条道路走到路口 $2$ ，所需费用为 $5$ 。
对于路口 $3$ ：小 Y 将参数 $p$ 增加 $1$ ，然后操控机器人沿以路口 $1$ 为起点的第 $2$ 条道路走到路口 $3$ ，所需费用为 $2 + 1 = 3$ 。
对于路口 $4$ ：小 Y 将参数 $p$ 增加 $1$ ，然后操控机器人沿以路口 $1$ 为起点的第 $2$ 条道路走到路口 $3$ ，再操控机器人沿以路口 $3$ 为起点的第 $2$ 条道路走到路口 $4$ ，所需费用为 $2 + 1 + 1 = 4$ 。

可以证明，上述移动方案的所需费用均为最小值。

对于路口 $5$ ：由于小 Y 无法将机器人移动到路口 $5$ ，因此输出 $-1$ 。

对于所有测试数据，保证：

来源

NOI