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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
int N, M, S, E, n[17][17], dp[17][65536], bit[17], trace[17][65536];
int min(int a, int b){
    if (a > b)return b;
    return a;
}
 
int main(){
    int i, j, k, maxx = 0, temp, h, sol = 99999999;
    scanf("%d", &N);
    for (i = 1; i <= N; i++){
        maxx += bit[i] = 1 << i - 1;
        for (j = 1; j <= N; j++){
            scanf("%d", &n[i][j]);
        }
    }
    for (i = 0; i <= maxx; i++){
        for (j = 0; j <= N; j++){
            dp[j][i] = 999999999;
        }
    }
    for (j = 1; j <= N; j++){
        dp[j][bit[j]] = 0;
        trace[j][bit[j]] = j;
    }
 
    for (i = 1; i <= maxx; i++){
        temp = i;
        for (k = N; k >= 1; k--){
            if (temp - bit[k] < 0)continue;
            temp -= bit[k];
            for (h = 1; h <= N; h++){
                if (n[h][k] == 0)continue;
                if (dp[k][i] > dp[h][i - bit[k]] + n[h][k]){
                    dp[k][i] = dp[h][i - bit[k]] + n[h][k];
                    trace[k][i] = trace[h][i - bit[k]];
                }
            }
        }
    }
 
    for (j = 1; j <= N; j++){
        dp[j][maxx] += n[j][trace[j][maxx]];
        sol = min(dp[j][maxx], sol);
    }
    i = 1;
    printf("%d", sol);
    return 0;
}
 
cs



비트마스킹 개념만 알고 있어서  이렇게 짯는데 다른 사람보다 10배 정도 느린거 같음

내가 짠 부분중 속도를 엄청 저하시키는 부분이 어디임?