简单的旅行商
说明
我们知道,旅行商问题是一个 $\text{NP-Hard}$ 问题,研究的是图中无重复访问点的最短路径。我们给定一个周长为 $C$ 的圆,在圆上有 $n$ 个节点.
从圆上某一点开始,沿着一个方向行走,在行走距离 $a_i$ 后有一个节点 $i$
你可以沿着圆周,从任意方向行走,这样我们就得到一个环状的无向图。
请你在图中找到一条路径,使得每个节点恰好访问一次,且路径长度最短.
请你输出这个最短路径的长度
输入格式
输入第一行,两个整数,$C,n$,分别代表圆的周长以及节点个数.输入第二行,$n$ 个递增的整数 $a_i$ ,代表每个节点在圆上的相对位置.
$ (2 \leq C \leq 10^6, 2 \leq n \leq 2 \times 10^5)$
$( 0 \leq a_1 < a_2 < ... < a_n < C)$
输出格式
输出一个整数,代表最短路径长度样例
20 3
5 10 1510统计
相关
在下列比赛中: