์ผ๋จ ํ์ ๋ง ์ ๋ฆฌํด๋๊ณ , ๋์ค์ ์ฌ๋์๊ฒ ์ ๋ฆฌํด๋ณผ ์์ .
int N;ll w[16][16];ll dp[1<<16][16];// bit dp// dp[4][110111]// 0, 1, 3, 4, 5 ๋ฒ์งธ ๋์๋ฅผ ๋ค๋ ๊ณ , 4๋ฒ์งธ ๋์๋ฅผ ๋ง์ง๋ง์ ๋ค๋ฅธ ์ํ์void solve() {scanf("%d", &N);FOR(i,0,N) {FOR(j,0,N) {scanf("%lld", &w[i][j]);}}memset(dp, 0x3F, sizeof(ll) * (1<<16) * 16);int allstate = 1 << N;for(int state = 1; state < allstate; ++state) {for(int cur = 0; cur < N; ++cur) {if ((1<<cur) & state) { // ์ด ๋๋ง ์ ํจํจif (__builtin_popcount(state) == 1) {if (w[0][cur]) dp[state][cur] = w[0][cur]; // 0์์ ์ถ๋ฐํ ๊ฒ์ผ๋ก ๊ณ ๋ฅธ๋ค.continue;}// ์ด์ ๊ธฐ์ค์ผ๋ก ํ๊ธฐint pstate = state ^ (1<<cur);for(int prev = 0; prev < N; ++prev) {if (cur == prev) continue;if (w[prev][cur] == 0) continue;if ((1<<prev) & state) { // ์ด์ ์ ์์ด์ผ ํจ! cur์ ์๋๊ฑฐ๊ณdp[state][cur] = min(dp[state][cur], dp[pstate][prev] + w[prev][cur]);}}// next ๊ธฐ์ค์ผ๋ก ํ๊ธฐ// for(int next = 0; next < N; ++next) {// if (cur == next) continue;// if (!((1<<next) & state)) continue; // state์ ์๋ ์ ๋ง ์ทจ๊ธํจ// if (w[cur][next] == 0) continue; // ๊ธธ ์์ด์ผ ํจ// dp[state][next] = min(dp[state][next], dp[state ^ (1<<next)][cur] + w[cur][next]);// }}}}// for(int i = 0; i < N; ++i) {// printf("%lld\n", dp[(1<<N) - 1][i]);// }printf("%lld\n", dp[(1<<N) - 1][0]); // 0: ํ๋ฐํด ๋๊ณ ๋ค์ 0์ผ๋ก ์ค๋ ๊ฒฝ์ฐ๋ฅผ ๋ด์ผ ํจ}