P11343 [KTSC 2023 R1] 出租车旅行

**请勿用 C++14 (GCC 9) 提交。** 请在程序开头加入如下代码： ```cpp #include std::vector travel(std::vector A, std::vector B, std::vector U, std::vector V, std::vector W); ```

**题目译自 [2023년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2023/) T3 「[택시 여행](https://assets.ioikorea.kr/ioitst/2023/1/taxi/taxi_statement.pdf)」** IOI 国由 $N$ 个城市和连接这些城市的 $N-1$ 条双向道路组成，任意两个不同的城市都可以通过这些道路互相到达。也就是说，IOI 国的道路网络是一个树结构。 每个城市都有一个编号，从 $0$ 到 $N-1$，其中 $0$ 号城市是 IOI 国的首都。对于每个 $i$ $(0 \leq i \leq N-2)$，第 $i$ 条道路连接 $U[i]$ 号城市和 $V[i]$ 号城市，道路长度为 $W[i]$ 公里。 在 IOI 国，不同城市的出租车费用不同。具体来说，对于每个 $i$ $(0 \leq i \leq N-1)$，从 $i$ 号城市出发的出租车有一个基本费用 $A[i]$ 元和每公里的费用 $B[i]$ 元。这意味着，如果从 $i$ 号城市出发并行驶 $d$ 公里，需要支付 $A[i] + d \times B[i]$ 元。 小明目前住在首都 $0$ 号城市，他计划乘坐出租车去其他城市旅行。当他到达一个城市时，可以选择继续乘坐当前的出租车，或者换乘该城市出发的出租车。当然，换乘出租车需要支付基本费用，并且每公里的费用也可能不同。请计算从 0 号城市出发到达其他所有城市的最小费用。 你需要实现以下函数： ```cpp vector travel(vector A, vector B, vector U, vector V, vector W); ``` - 该函数只会被调用一次。 - `A`：大小为 $N$ 的整数数组。对于每个 $i$ $(0 \leq i \leq N-1)$，$A[i]$ 是从 $i$ 号城市出发的出租车的基本费用。 - `B`：大小为 $N$ 的整数数组。对于每个 $i$ $(0 \leq i \leq N-1)$，$B[i]$ 是从 $i$ 号城市出发的出租车的每公里费用。 - `U, V, W`：大小为 $N-1$ 的整数数组。对于每个 $i$ $(0 \leq i \leq N-2)$，$U[i]$ 号城市和 $V[i]$ 号城市之间有一条长度为 $W[i]$ 公里的道路。 - 该函数返回一个大小为 $N-1$ 的数组 $C$。对于每个 $i$ $(0 \leq i \leq N-2)$，$C[i]$ 是从 $0$ 号城市出发到达 $i+1$ 号城市的最小费用。 注意，提交的代码中不应包含任何输入输出操作。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N$ - 第 $2$ 行：$A[0]\,A[1]\,\cdots\,A[N-1]$ - 第 $3$ 行：$B[0]\,B[1]\,\cdots\,B[N-1]$ - 第 $4+i$ $(0 \leq i \leq N-2)$ 行：$U[i]\,V[i]\,W[i]$

示例评测程序按以下格式输出： - 第 $i$ 行：函数 `travel` 返回的数组的第 $i$ 个元素

### 样例解释 考虑 $N=5, A=[10,5,13,4,3], B=[10,7,5,9,1], U=[1,0,3,2], V=[0,2,2,4], W=[1,5,10,3]$ 的情况。 评测程序将调用如下函数： ```cpp travel([10, 5, 13, 4, 3], [10, 7, 5, 9, 1], [1, 0, 3, 2], [0, 2, 2, 4], [1, 5, 10, 3]); ``` - 从 $0$ 号城市到 $1$ 号城市的最优方案是直接从 $0$ 号城市乘坐出租车，总费用为 $20$ 元。 - 从 $0$ 号城市到 $2$ 号城市的最优方案是直接从 $0$ 号城市乘坐出租车，总费用为 $60$ 元。 - 从 $0$ 号城市到 $4$ 号城市的最优方案是先从 $0$ 号城市乘坐出租车到 $1$ 号城市，然后换乘，再经过 $0$ 号和 $2$ 号城市到达 $4$ 号城市，总费用为 $88$ 元。 - 从 $0$ 号城市到 $3$ 号城市的最优方案是先从 $0$ 号城市乘坐出租车到 $1$ 号城市，然后换乘，再经过 $0$ 号和 $2$ 号城市到达 $4$ 号城市，再换乘，经过 $2$ 号城市到达 $3$ 号城市，总费用为 $104$ 元。 函数应返回 `[20, 60, 104, 88]`。 ### 数据范围 对于所有输入数据，满足： - $2 \leq N \leq 10^5$ - 对于所有 $i$ $(0 \leq i \leq N-1)$，$0 \leq A[i] \leq 10^{12}$ - 对于所有 $i$ $(0 \leq i \leq N-1)$，$0 \leq B[i] \leq 10^6$ - 对于所有 $i$ $(0 \leq i \leq N-2)$，$0 \leq U[i], V[i] \leq N-1 ; U[i] \neq V[i]$ - 对于所有 $i$ $(0 \leq i \leq N-2)$，$1 \leq W[i] \leq 10^6$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $7$ | $N \leq 20$ | | $2$ | $8$ | 对于所有 $i$ $(0 \leq i \leq N-2)$，$U[i]=i ; V[i]=i+1$ | | $3$ | $13$ | $N \leq 2000$ | | $4$ | $17$ | 对于所有 $i$ $(0 \leq i \leq N-1)$，$B[i] \leq 30$ | | $5$ | $29$ | $B[i] \neq 0$ $(0 \leq i \leq N-1)$ 的 $i$ 不超过 $2000$ 个 | | $6$ | $26$ | 无附加限制 |