题目链接
状态表示:f[i][j]
i为储存的状态,j为当前从0=>j最后经过的一个点的值,f[i][j]
的值为经过的路径总长度。
那么对于$k\in [1…n]$,有
$$
f[i,j]=\min{f[i-1<<k, j-{k}]+distance(k\rightarrow j)}
$$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| #include <bits/stdc++.h> using namespace std; const int N = 20, M = 1 << N; int f[M][N]; int m[N][N]; int n; int main() { scanf("%d", &n); int _m = 1 << n; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d", &m[i][j]); memset(f, 0x3f, sizeof f); f[1][0] = 0, f[0][0] = 0; for(int i = 0; i < _m; ++i) { for(int j = 0; j < n; ++j) { if((i >> j) & 1) { for(int k = 0; k < n; ++k) { if(((i>>k)&1) && k != j) f[i][j] = min(f[i][j], f[i-(1<<j)][k] + m[k][j]); } } } } printf("%d", f[_m-1][n-1]); return 0; }
|