# 11088: 【原1088】邮递员小F

### 题目描述

author: wcy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1088

## Input Format

$$1 \leq N \leq 15$$

$$0 \leq Aij \leq 2000$$

## Sample Input

4
0 6 7 9
6 0 6 5
7 6 0 8
9 5 8 0


## Sample Output

26


## BugenZhao's solution

//
// Created by BugenZhao on 2019/5/17.
//

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;

unsigned N;
int d[15][15];
const int statusCount = 1U << 16U;
int dp[15][statusCount];

int getBit(unsigned num) {
unsigned k = 1;
int ans = 0;
while (k <= 2 * num) {
ans += (bool) (num & k);
k <<= 1U;
}
return ans;
}

int getAns(int cur, unsigned status) {
if (dp[cur][status] != -1) return dp[cur][status];
if (getBit(status) == 2) {
dp[cur][status] = d[0][cur];
return dp[cur][status];
}

int ret = 0x7fffffff;
for (unsigned i = 1; i < N; ++i) {
if (i == cur) continue;
if (status & (1U << i)) {
int ans = getAns(i, status - (1U << cur)) + d[i][cur];
if (ans < ret) ret = ans;
}
}
dp[cur][status] = ret;
return ret;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> d[i][j];
}
}

if (N == 1) {
cout << 0 << endl;
return 0;
}

for (int i = 0; i < 15; ++i) {
for (int j = 0; j < statusCount; ++j) {
dp[i][j] = -1;
}
}

int minAns = 0x7fffffff;
dp[0][1] = 0;
for (int i = 1; i < N; ++i) {
int ans = d[0][i] + getAns(i, (1U << N) - 1);
if (minAns > ans) minAns = ans;
}
cout << minAns << endl;
return 0;

}


## FineArtz's solution

/* 邮递员小F */
#include <iostream>
#include <cstring>
using namespace std;

const int INF = 2000000000;

int n;
int a[16][16];
int f[16][32768];

int main(){
cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
cin >> a[i][j];
if (n == 1){
cout << 0 << endl;
return 0;
}
for (int i = 1; i <= (1 << n) - 1; i += 2){
for (int j = 2; j <= n; ++j){
if (i & (1 << (j - 1))){
if (i ^ ((1 << (j - 1)) + 1)){
f[j][i] = INF;
for (int k = 2; k <= n; ++k){
if (k != j && i & (1 << (k - 1))){
f[j][i] = min(f[j][i], f[k][i ^ (1 << (j - 1))] + a[k][j]);
}
}
}
else
f[j][i] = a[1][j];
}
}
}
int ans = INF;
for (int i = 2; i <= n; ++i){
ans = min(ans, f[i][(1 << n) - 1] + a[i][1]);
}
cout << ans << endl;
return 0;
}


## ligongzzz's solution

#include <iostream>
using namespace std;

int map_data[20][20] = { 0 };

int mmin(int a, int b) {
return a < b ? a : b;
}

bool visited[20] = { 0 };
int n;

int dfs(int pos, int m) {
if (m == n - 1) {
return map_data[pos][0];
}
visited[pos] = true;
int ans = 999999999;
for (int i = 0; i < n; ++i) {
if (i != pos && !visited[i]) {
auto cur_ans = dfs(i, m + 1) + map_data[pos][i];
ans = cur_ans < ans ? cur_ans : ans;
}
}
visited[pos] = false;
return ans;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

cin >> n;

for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> map_data[i][j];

/*
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
map_data[i][j] = mmin(map_data[i][j], map_data[i][k] + map_data[k][j]);
}
}
}*/

cout << dfs(0, 0);

return 0;
}


## yyong119's solution

#include <iostream>
using namespace std;
int n;
int map[16][16];
int cost;
bool flag[16];

void dfs(int depth, int temp, int pos) {

if (temp >= cost) return;
if (depth == n){
if (temp + map[pos][1] < cost) cost = temp +map[pos][1];
return;
}
for (int i = 2; i <= n; i++)
if ((!flag[i])&&(i != pos)) {
flag[i] = true;
dfs(depth+1, temp + map[pos][i], i);
flag[i] = false;
}
}
int main() {

cin>>n;
cost = 2000 * 15;

for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
cin>>map[i][j];
}
dfs(1,0,1);
cout<<cost;
}