Untitled

 avatar
unknown
plain_text
a year ago
869 B
6
Indexable
#include <iostream>

using namespace std;

int n;
const int MN = 15;
int dist[MN][MN];

bool visited[MN];
int per[MN];
int ans = 1e9;

void dfs(int i, int cost) {
    if (ans < cost) {
        return;
    }
    if (i == n) {
        ans = min(ans, cost + dist[per[n - 1]][0]);
        return;
    }
    for (int j = 1; j < n; ++j) {
        if (visited[j]) {
            continue;
        }
        visited[j] = true;
        per[i] = j;
        dfs(i + 1, cost + dist[per[i - 1]][per[i]]);
        visited[j] = false;
    }
}

int main()
{
    int t;
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> dist[i][j];
            }
        }
        per[0] = 0;
        ans = 1e9;
        dfs(1, 0);
        cout << ans << '\n';
    }
    return 0;
}
Editor is loading...
Leave a Comment