#1053. 星际争霸

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: TosakaUCW

题目描述

在一个名为 “Guanyue1234” 的神秘星球上,存在着一种由 0 到 n − 1 号共 n 个城市构成的独特布局。城市 1 到 n − 1 形成一个大的环状结构,每个城市都通过双向道路与它的相邻城市连接。星球的行政中心,Guanyue 校长别墅,即编号为 0 的城市,位于环的中心,并直接通过双向道路与环上的每个城市相连。

Guanyue1234 星球的科技高度发达,城市间的能源传输效率成为了研究的重点。为了优化能源分配和增强系统的稳定性,Tony102 计划在两个能源传输效率最低的城市之间建立一个先进的能源中继站。

因此,任务是找出两个在最短路径距离上最遥远的城市,这两个城市之间的能源传输效率预计是最低的,建立能源中继站可以显著提高整个星球的能源管理效率。由于中心城市与所有外围城市均有直接连接,这增加了问题的复杂性,需要考虑城市之间的直接距离以及它们通过首都的间接距离。

挑战在于开发一个高效的算法,用以确定所有可能的城市对中,哪一对的最短路径距离最长。这将为建立能源中继站提供关键数据,并影响未来的基础设施规划和能源布局。请编写一个程序,找出并返回这两个城市之间的最短路径长度。

输入格式

第一行包含一个正整数 , 表示城市的数量。

第二行包含 个正整数 , 其中 表示城市 与城市 之间的双向道路的长度, 表示城市 与城市 1 之间的双向道路的长度。

第三行包含 个正整数 , 其中 表示城市 与首都之间的双向道路的长度。

输出格式

输出一行一个整数, 即最遥远的两个城市之间的最短路的长度。

样例

输入样例1

6
1 4 5 1 6
3 5 1 8 2

输出样例1

7

最遥远的城市为城市 2 和城市 4 , 它们之间的最短路长度为 7 。

数据范围与提示

对于 的数据,

测试点编号
1,2
3,4