求助为何超时???马蜂良好
查看原帖
求助为何超时???马蜂良好
1054952
zzCX_df楼主2024/8/6 09:15

nn明明是最大2020,为何会超时?,算的时间复杂度也没超时呀?

#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;
}
2024/8/6 09:15
加载中...