#include<cstdio> #include<algorithm> using namespace std; int n, dp[1 << 16][16], w[16][16]; int f(int x, int y) { if (x == (1 << n) - 1) return w[y][0] ? w[y][0] : 1e9; if (!dp[x][y]) { dp[x][y] = 1e9; for (int i = 0; i<n; i++) if (w[y][i] && !(x & 1 << i)) dp[x][y] = min(dp[x][y], f(x | 1 << i, i) + w[y][i]); } return dp[x][y]; } int main() { scanf("%d", &n); for (int i = 0; i<n; i++) for (int j = 0; j<n; j++) scanf("%d", &w[i][j]); printf("%d", f(1, 0)); return 0; }
2098번: 외판원 순회
https://www.acmicpc.net/problem/2098
라벨:
풀이쓸예정
,
Bit Mask
,
BOJ
,
travelling salesman problem
피드 구독하기:
댓글
(
Atom
)
댓글 없음 :
댓글 쓰기