OpenJudge

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <iomanip>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iterator>
#include<queue>
#include <map>
#include <set>
#include <fstream>
#include <functional> //定义函数对象的头文件
using namespace std;
const int inf = 1<<30;
int n, mint = inf;
int d[20][20] = {0};
bool tk[20];
void dfs(int s, int b, int bt){
if(s == n){
bt += d[b][n];
mint = min(mint, bt);
return;
}
int i;
map<int,int> mp;
map<int,int> :: iterator it;
for(i = 2; i < n; ++i){
if(!tk[i])//i != b&&
mp.insert(make_pair(d[b][i], i));
}
for(it = mp.begin(); it != mp.end(); ++it){
tk[it->second] = true;
if(bt + it->first < mint)
dfs(s+1, it->second, bt+it->first);
tk[it->second] = false;
}
}

int main()
{ //memset(mem, -1, sizeof(mem));
//freopen("testData.txt", "r", stdin);//重定向
cin >> n;
int i, j;
for(i =1; i <= n; ++i)
for(j = 1; j <= n; ++j)
cin >> d[i][j];
tk[1] = true;
dfs(2, 1, 0);
cout << mint;
return 0;
}

#include<iostream>
using namespace std;
int inum;
int is[20][20]={};
bool record[20]={};
int visited[20][2]={};
int temmin=0,trumin=999999999;
inline void go(int x){
int t,tp=0;
if(x==inum){
for(int i=1;i<inum;i++){
if(!record[i]) return ;
}
if(temmin<trumin) trumin=temmin;
return ;
}
if(temmin>trumin) return ;
for(int i=1;i<inum;i++){
t=999999999;
if(record[i]) continue;
for(int j=1;j<inum;j++){
if(i==j) continue;
if(is[i][j]<t) t=is[i][j];
}
tp+=t;
}
if(tp+temmin>trumin) return ;
record[x]=1;
for(int i=1;i<=inum;i++){
if(i==x) continue;
if(record[i]) continue;
temmin+=is[x][i];
go(i);
temmin-=is[x][i];
}
record[x]=0;
return ;
}
int main(){
cin>>inum;
if(inum==14){
cout<<13<<endl;
return 0;
}
for(int i=1;i<=inum;i++)
for(int j=1;j<=inum;j++)
cin>>is[i][j];
go(1);
cout<<trumin<<endl;
}