http://codeup.hustoj.com/problem.php?cid=100000575&pid=4

题目描述

The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

输入

Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances D1 D2 ... DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (<=104), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 107.

输出

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

样例输入 

5 1 2 4 14 9 

3 

1 3 

2 5 

4 1

样例输出 

3 

10 

7

/*《算法笔记》上解释的非常详细，下面是我的理解 

输入解释：第一行的5就是有5个节点，后面的5个数是相邻节点1-2，2-3......5-1的距离

第二行的3指的是我们要求三组节点之间的最短路径

第三行就是求第1个节点到第3个节点的距离

......以此类推 

题目的大概要求就是有一个圆，圆上有n个节点，每个节点间都给出了距离，

然后去求某个节点到某个节点之间的最短距离，而且每次只能移动到相邻节点。

那么怎么做呢？

首先，它限制了只能移动到相邻节点，也就是说一个节点只能顺时针或逆时针移动

（不会有人抬杠，这个节点顺时针走一次，再逆时针走一次吧）

所以说，问题就变得简单了，我们只要比较它是逆时针和逆时针哪个是最短距离就好了

首先我们需要有一个记录总路程的sum，和一个记录每一次输入两点之间距离的数组A[i]

在输入每个距离的时候，把它加到sum上就很容易得出总路程。

我们还要有个记录某个点到某个点（顺/逆时针）的距离temp，我一开始想用循环，把某个节点

到某个节点的距离加起来，参考了答案后，可以看出它用了一个更容易的方法

就是我们在求sum的时候可以得到第1个节点到其他i个节点的距离dis[]，比如我们想要得到第2个节点

到第5个节点的距离，我们就可以用1到5的距离减去1到2的距离，如图2，再用min函数（用c++的原因）

求出最小值。*/