啊。。。水题 = =。。。
好久好久以前就看到这题了，无奈special judege 和冗长的题目让我望而却步咧。。。
今天鼓起勇气。。。读了下题。。。
啊。。。水题 = =。。。
给你N个城市，已经存在高速从编号小的到编号大的，比如1->2->3->4->5...
让你连接两条高速，使得每个城市都可以到达另一个城市。（两条高速不可以连接同一个城市，必须俩不同的城市）。
我的思路是，1号必须被到达，n号必须出发一条。然后两条的话，就从n到i 然后从i+1到1，肯定是这两条无疑 = =。。。找加和最短的即可。
循环的时候i不可以取1，WA了几次 = =。。。。
#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> using namespace std; int city[50010]; int main() { int mid,ncases,n,i; scanf("%d",&ncases); while(ncases--) { scanf("%d",&n); for(i=2; i<=n; i++) scanf("%d",&city[i]); city[1] = 0; mid = -1; int min = INT_MAX; for(i=n-2; i>1; i--) if( city[n] - city[i] + city[i+1] - city[1] < min ) { min = city[n] - city[i] + city[i+1] - city[1]; mid = i; } if( mid == -1 || n <= 3 ) printf("0/n/n"); else printf("%d/n%d %d %d %d/n/n",min,mid+1,1,n,mid); } return 0; }
