题目描述 Description
有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），最后还要回到0点（他的单位），请问最短时间是多少。现在已知任意两个城市的直接通路的时间。
输入描述 Input Description
第一行一个正整数n （1<=n<=15）
接下来是一个（n+1）*(n+1)的矩阵，矩阵中的数均为不超过10000的正整数。矩阵的i行j列表示第i-1号城市和j-1号城市之间直接通路的时间。当然城市a到城市b的直接通路时间和城市b到城市a的直接通路时间不一定相同，也就是说道路都是单向的。
输出描述 Output Description
一个正整数表示最少花费的时间
样例输入 Sample Input
3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
样例输出 Sample Output
8
数据范围及提示 Data Size & Hint
1<=n<=15
/*
把去过哪个城市压成一个数，表示状态，然后跑最短路（其实也可以直接dp递推，但是最短路更自然）
主要codevs上有一个sb测试点，16*16的矩阵他给了个15*15的，对付什么样的sb数据用什么样的sb办法
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct orz{
int d,p1,p2;
friend bool operator < (orz a,orz b){
return a.d > b.d;
}
};
int n,e[][],d[<<][];
priority_queue < orz > ss;
int flag = ,vis[<<][];
int read(){
char ch=getchar();
int x=,f=;
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
void floyd(){
for(int k = ;k <= n;k++){
for(int i = ;i <= n;i++){
for(int j = ;j <= n;j++){
if(k != i && k != j && i != j && e[i][j] > e[i][k] + e[k][j]){
e[i][j] = e[i][k] + e[k][j];
}
}
}
}
}
void dij(){
d[][] = ;
orz tmp;
tmp.d = ;
tmp.p1 = tmp.p2 = ;
ss.push(tmp);
flag++;
int to1,to2,dd,tlg;
while(!ss.empty()){
tmp = ss.top();
ss.pop();
dd = tmp.d;
to1 = tmp.p1;
to2 = tmp.p2;
if(vis[to1][to2] == flag) continue;
vis[to1][to2] = flag;
for(int nxt = ,lg = ;nxt <= n;lg <<= ,nxt++){
tlg = (lg >> );
if(!(to1 & tlg) && d[to1+tlg][nxt] > d[to1][to2] + e[to2][nxt]){
d[to1+tlg][nxt] = d[to1][to2] + e[to2][nxt];
tmp.d = d[to1+tlg][nxt];
tmp.p1 = to1+tlg;
tmp.p2 = nxt;
ss.push(tmp); }
}
}
}
int main(){
n = read();
//bool bg = true;
for(int i = ;i <= n;i++){
for(int j = ;j <= n;j++){
e[i][j] = read();
//if(i == 0 && j > 0 && e[i][j] != 1) bg = false;
}
/*if(i > 0 && n == 15 && bg){
cout<<13;
return 0;
}*/
}
memset(d,/,sizeof(d));
floyd();
dij();
cout<<d[(<<n)-][];
return ;
}