# PAT 解题报告 1046. Shortest Distance (20)

### 1046. Shortest Distance 题目描述：

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.

### 1046. Shortest Distance 算法分析：

```#include <iostream>
#include <fstream>
#include <sstream>

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#include <algorithm>
#include <string>
#include <vector>

#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;

int main(void) {
int N, M;
int dist[100005];
cin>>N;
REP(i, N) cin>>dist[i];
cin>>M;
int tot = 0;
int distFromZero[100005];
memset(distFromZero, 0, sizeof(distFromZero));
distFromZero[1] = dist[0];
REP(i, N) {
distFromZero[i+1] = dist[i] + distFromZero[i] ;
tot += dist[i];
}

int a, b;
int c;
REP(i, M) {
cin>>a>>b;
if(a > b) {
c = a;
a = b;
b = c;
}
a--;
b--;
int di = distFromZero[b] - distFromZero[a];
cout<<min(di, tot-di)<<endl;
}
return 0;
}
```
Written on January 19, 2014