n明明是最大20,为何会超时?,算的时间复杂度也没超时呀?
#include <bits/stdc++.h>
typedef unsigned int us;
using namespace std;
us n, ans = 60000, f[21][1 << 20], a[21][21];
inline void dfs(us p, us now) {
for (us i = 1; i <= n; i++)
if (!((1 << (i - 1)) & now)) {
f[i][(1 << (i - 1)) | now] = min(f[i][(1 << (i - 1)) | now], f[p][now] + a[p][i]);
dfs(i, (1 << (i - 1)) | now);
}
}
inline void write(us x) {
if (x) {
write(x / 10);
putchar(x % 10 + '0');
}
}
signed main() {
memset(f, 127, sizeof(f));
scanf("%d", &n);
for (us i = 1; i <= n; i++)
for (us j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
f[1][1] = 0;
dfs(1, 1);
for (us i = 2; i <= n; i++)
ans = min(ans, f[i][(1 << n) - 1] + a[i][1]);
if (!ans) {
puts("0");
return 0;
}
write(ans);
return 0;
}