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個節(jié)點，后面的5個數(shù)是相鄰節(jié)點1-2，2-3......5-1的距離

第二行的3指的是我們要求三組節(jié)點之間的最短路徑

第三行就是求第1個節(jié)點到第3個節(jié)點的距離

......以此類推?

題目的大概要求就是有一個圓，圓上有n個節(jié)點，每個節(jié)點間都給出了距離，

然后去求某個節(jié)點到某個節(jié)點之間的最短距離，而且每次只能移動到相鄰節(jié)點。

那么怎么做呢？

首先，它限制了只能移動到相鄰節(jié)點，也就是說一個節(jié)點只能順時針或逆時針移動

（不會有人抬杠，這個節(jié)點順時針走一次，再逆時針走一次吧）

所以說，問題就變得簡單了，我們只要比較它是逆時針和逆時針哪個是最短距離就好了

首先我們需要有一個記錄總路程的sum，和一個記錄每一次輸入兩點之間距離的數(shù)組A[i]

在輸入每個距離的時候，把它加到sum上就很容易得出總路程。

我們還要有個記錄某個點到某個點（順/逆時針）的距離temp，我一開始想用循環(huán)，把某個節(jié)點

到某個節(jié)點的距離加起來，參考了答案后，可以看出它用了一個更容易的方法

就是我們在求sum的時候可以得到第1個節(jié)點到其他i個節(jié)點的距離dis[]，比如我們想要得到第2個節(jié)點

到第5個節(jié)點的距離，我們就可以用1到5的距離減去1到2的距離，如圖2，再用min函數(shù)（用c++的原因）

求出最小值。*/