Untitled
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