题目背景
请勿用 C++14 (GCC 9) 提交。
请在程序开头加入如下代码:
题目描述
题目译自 2023년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T3 「택시 여행」
IOI 国由 N 个城市和连接这些城市的 N−1 条双向道路组成,任意两个不同的城市都可以通过这些道路互相到达。也就是说,IOI 国的道路网络是一个树结构。
每个城市都有一个编号,从 0 到 N−1,其中 0 号城市是 IOI 国的首都。对于每个 i (0≤i≤N−2),第 i 条道路连接 U[i] 号城市和 V[i] 号城市,道路长度为 W[i] 公里。
在 IOI 国,不同城市的出租车费用不同。具体来说,对于每个 i (0≤i≤N−1),从 i 号城市出发的出租车有一个基本费用 A[i] 元和每公里的费用 B[i] 元。这意味着,如果从 i 号城市出发并行驶 d 公里,需要支付 A[i]+d×B[i] 元。
小明目前住在首都 0 号城市,他计划乘坐出租车去其他城市旅行。当他到达一个城市时,可以选择继续乘坐当前的出租车,或者换乘该城市出发的出租车。当然,换乘出租车需要支付基本费用,并且每公里的费用也可能不同。请计算从 0 号城市出发到达其他所有城市的最小费用。
你需要实现以下函数:
- 该函数只会被调用一次。
A
:大小为 N 的整数数组。对于每个 i (0≤i≤N−1),A[i] 是从 i 号城市出发的出租车的基本费用。
B
:大小为 N 的整数数组。对于每个 i (0≤i≤N−1),B[i] 是从 i 号城市出发的出租车的每公里费用。
U, V, W
:大小为 N−1 的整数数组。对于每个 i (0≤i≤N−2),U[i] 号城市和 V[i] 号城市之间有一条长度为 W[i] 公里的道路。
- 该函数返回一个大小为 N−1 的数组 C。对于每个 i (0≤i≤N−2),C[i] 是从 0 号城市出发到达 i+1 号城市的最小费用。
注意,提交的代码中不应包含任何输入输出操作。
输入格式
示例评测程序按以下格式读取输入:
- 第 1 行:N
- 第 2 行:A[0]A[1]⋯A[N−1]
- 第 3 行:B[0]B[1]⋯B[N−1]
- 第 4+i (0≤i≤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] 的情况。
评测程序将调用如下函数:
- 从 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≤N≤105
- 对于所有 i (0≤i≤N−1),0≤A[i]≤1012
- 对于所有 i (0≤i≤N−1),0≤B[i]≤106
- 对于所有 i (0≤i≤N−2),0≤U[i],V[i]≤N−1;U[i]=V[i]
- 对于所有 i (0≤i≤N−2),1≤W[i]≤106
详细子任务附加限制及分值如下表所示。
子任务 |
分值 |
附加限制 |
1 |
7 |
N≤20 |
2 |
8 |
对于所有 i (0≤i≤N−2),U[i]=i;V[i]=i+1 |
3 |
13 |
N≤2000 |
4 |
17 |
对于所有 i (0≤i≤N−1),B[i]≤30 |
5 |
29 |
B[i]=0 (0≤i≤N−1) 的 i 不超过 2000 个 |
6 |
26 |
无附加限制 |