真是一道坑爹的题目，题目其实说的不是很清晰。。。
WA了2次。。。
[题意] 在一条单向公路上，有n个村庄，第i个村庄只能到i以后的村庄，而不能到i之前的村庄(因为是单行道)。新村长要建两条新路，使得各个村庄之间都能走通(一条反向的就可以，为什么要建两条？题目说了，只建一条不足矣增加自己的政绩)
[思路] 找出所有路段中最短的，加上原来的总长，就是答案。有一点要注意，题目说两条路的4个端点必须不同，因此要排除端点重合的问题。另外，n=2和n=3是无解的。
我们知道要满足条件，那么我们就必定使1~n有通路，我们可以从1~n修一条路，在从n-3条边选出最短的边就可以了；这里为什么是从n-3条边里选，这里我们要去掉两个端点的边；
例如：n=4 时 4 7 9，这里答案是12而不是11；
#include <stdio.h>int main()
{int N; //有N个村庄scanf("%d",&N);int pos; //临时保存各个村庄现在的坐标点int pre=0; //临时保存村庄过去的坐标点int sum=0;int i;int minRoad=0x7fffffff;int start;for(i=2;i<=N;i++){//输入每个村庄pos坐标，村庄1的坐标为0scanf("%d",&pos);sum+=(pos-pre);if (i!=2 && i!=N && pos-pre<minRoad){minRoad=pos-pre;start=i-1;}pre=pos;}if (N<4){printf("0\n");return 0;}printf("%d\n",sum+minRoad);//printf("%d %d %d %d\n",start+1,1,N,start);printf("%d %d %d %d\n",N,1,start,start+1); //居然都AC了return 0;
}根本不用sum，本来就会输入总和的：
#include <stdio.h>int main()
{int N; //有N个村庄scanf("%d",&N);int pos; //临时保存各个村庄现在的坐标点int pre=0; //临时保存村庄过去的坐标点int i;int minRoad=0x7fffffff;int start;for(i=2;i<=N;i++){//输入每个村庄pos坐标，村庄1的坐标为0scanf("%d",&pos);if (i!=2 && i!=N && pos-pre<minRoad){minRoad=pos-pre;start=i-1;}pre=pos;}if (N<4){printf("0\n");return 0;}printf("%d\n",pos+minRoad);//printf("%d %d %d %d\n",start+1,1,N,start);printf("%d %d %d %d\n",N,1,start,start+1); //居然都AC了return 0;
}