www.rqnoj.cn/Problem_301.html
晕。。竟然抄TopCoder的原题。。
看上去很难，因为10^10的搜索是要悲剧的。。但实际上只要每个点中间点向左向右搜出10^5的路径然后都排序就可以直接扫描得出结果了。。
Code：
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>2,maxn=10,maxp=100000+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct Array
{
double A[maxp];int n;
void set(){n=0;}
Array(){set();}
void add(double x){A[n++]=x;}
void Sort(){sort(A,A+n);}
double operator[](int v){return A[v];}
};
int n;double D[maxn][maxn];
Array L,R;
void DfsL(int pos,int d,double now)
{
if(!d){L.add(now);return;}
rep(i,n)DfsL(i,d-1,now+D[i][pos]);
}
void DfsR(int pos,int d,double now)
{
if(!d){R.add(now);return;}
rep(i,n)DfsR(i,d-1,now+D[pos][i]);
}
int main()
{
//freopen("in","r",stdin);
cin>>n;rep(i,n)rep(j,n){cin>>D[i][j];}
double ans=inf;
rep(i,n)
{
int l=n/2,r=n-l;
L.set();R.set();
DfsL(i,l,0);DfsR(i,r,0);
L.Sort();R.add(inf);R.add(-inf);R.Sort();int j=R.n-1;
for(int i=0;i<L.n;i++)
{
while(L[i]+R[j]>=2007)j–;
ans=min(ans,2007-L[i]-R[j]);
ans=min(ans,L[i]+R[j+1]-2007);
}
}
printf("%0.2lfn",ans);
}