#P9789. 图的直径
图的直径
题目描述
有两条无向链。每条链各有 个点,编号为 。第一条链中,编号为 和 的点之间的边长为 。第二条链中,对应边长为 。
从 中选择 个不同的编号。对每个选中的编号 ,在两条链的 号点之间加入一条长度为 的无向边。
图的直径是任意两点之间最短路长度的最大值。求添加零边之后可能达到的最小直径。
输入格式
第一行两个整数 。第二行 个整数 。第三行 个整数 。
输出格式
输出一行一个整数,表示最小直径。
样例
5 4
2 1 1 1 2
1 9 1 9 1
6
原赛样例 2–4 见下发文件。
数据范围
,,。
| 原赛子任务 | 特殊限制 | 原赛分值 |
|---|---|---|
| 1 | 30 | |
| 2 | 20 | |
| 3 | ||
| 4 | 无 | 30 |