1357: 厦门市中小学复赛2023第三题 太空旅行

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：5 Solved：2

Description

在未来，太空旅行已经是一件稀松平常的事，星际部又宣称即将开通一条 火星至天王星的航线。 所有的星际飞船必须先经过航线 1（地球—>火星），再经过航线 X（火星 —>天王星）才能顺利抵达天王星。 为了避免星际飞船发生碰撞，每条航线只能有一架飞船正在行驶。 已知星际飞船从地球到火星需要 U(i)时间，火星到天王星需要 V(i)时间。 飞船们可能会滞留在火星，它们必须等待航线状态为空才能起飞。飞船到 达火星和离开火星的顺序可能会不一致。 请计算从地球出发的 N 架星际飞船，全部抵达天王星，需要花费的最短时 间。

Input

从文件 travel.in 中读入数据。 第 1 行：一个整数 N，表示星际飞船的数量。 第 2 到 N+1 行：第 i+1 行包含两个空格隔开的整数：U(i) 和 V(i)。

Output

输出到文件 travel.out 中。 输出 1 行，一个单独的整数，表示所有飞船抵达天王星需要的最短时间。

Sample Input Copy 

3
6 4
8 1
2 3

Sample Output Copy 

17

HINT

【样例解释】

最优方案总耗时为： 2+6+8+1 = 17。 

 地球—>火星出发  地球—>火星到达  火星—>天王星出发 火星—>天王星到达
第 1 架 2 8 8 12
第 2 架 8 16 16 17
第 3 架 0 2 2 5
【数据范围】

测试点编号 特殊性质   1<=N<=    1<=U(i),V（i）<=

0~1            无              10                100
2~7            无              100               500
8~11          无              10000            5000
12~13         B               25000            50000
14~15         A               25000            50000
16~19        无               25000            50000
其中：
特殊性质 A：保证所有的 U(i)都相同。
特殊性质 B：保证所有的 V(i)都相同。

Source/Category

SubmitSubmit RecordStatistics