编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#114509 #1450. 售货员问题 Accepted 100 89 ms 2320 K C / 1.0 K 纯真丁一郎 2024-07-14 23:05:59
显示原始代码
#include <stdio.h>
#include <limits.h>

#define MAXN 16
#define INF INT_MAX

int n;
int dist[MAXN][MAXN];
int dp[1 << MAXN][MAXN];

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int tsp(int mask, int pos) {
    if (mask == (1 << n) - 1) {
        return dist[pos][0];
    }

    if (dp[mask][pos] != -1) {
        return dp[mask][pos];
    }

    int answer = INF;
    for (int city = 0; city < n; city++) {
        if ((mask & (1 << city)) == 0) {
            int newAnswer = dist[pos][city] + tsp(mask | (1 << city), city);
            answer = MIN(answer, newAnswer);
        }
    }

    return dp[mask][pos] = answer;
}

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &dist[i][j]);
        }
    }

    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = -1;
        }
    }

    int result = tsp(1, 0);
    printf("%d\n", result);

    return 0;
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:3 ms
内存:256 KiB

输入文件(1.in

5
0 97 39 24 8 
43 0 95 18 17 
12 38 0 79 17 
78 94 29 0 30 
89 46 39 69 0 

答案文件(1.out

113

用户输出

113

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:4 ms
内存:256 KiB

输入文件(2.in

7
0 52 20 64 59 35 97 
99 0 97 25 3 35 53 
98 3 0 76 74 38 46 
95 24 21 0 68 18 89 
8 76 60 34 0 56 
<46 bytes omitted>

答案文件(2.out

144

用户输出

144

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:2 ms
内存:324 KiB

输入文件(3.in

10
0 61 14 11 62 88 78 40 15 56 
50 0 58 1 60 52 98 3 43 90 
60 58 0 60 7 1 76 90 19 52 
4 31 79 0 7
<194 bytes omitted>

答案文件(3.out

135

用户输出

135

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:5 ms
内存:452 KiB

输入文件(4.in

12
0 67 99 24 67 54 40 3 36 83 10 51 
48 0 17 38 16 25 29 41 1 27 100 65 
18 59 0 32 48 74 8 10 98 9
<325 bytes omitted>

答案文件(4.out

131

用户输出

131

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:9 ms
内存:1232 KiB

输入文件(5.in

14
0 27 97 77 55 80 9 71 56 91 51 36 32 30 
86 0 2 94 67 69 100 10 23 21 11 2 65 57 
67 33 0 39 99 9
<480 bytes omitted>

答案文件(5.out

166

用户输出

166

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:12 ms
内存:2264 KiB

输入文件(6.in

15
0 1 13 21 60 45 4 3 78 18 12 56 22 25 43 
4 0 16 52 88 41 78 93 26 90 60 4 31 95 55 
87 18 0 18 6
<554 bytes omitted>

答案文件(6.out

93

用户输出

93

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:13 ms
内存:2320 KiB

输入文件(7.in

15
0 59 34 70 50 52 53 94 88 94 20 32 74 75 8 
52 0 81 75 83 35 66 84 17 66 27 2 98 99 59 
91 61 0 9
<557 bytes omitted>

答案文件(7.out

167

用户输出

167

系统信息

Exited with return code 0
测试点 #8
Accepted
得分:100
用时:14 ms
内存:2244 KiB

输入文件(8.in

15
0 84 55 20 73 91 35 85 99 70 28 8 93 24 72 
68 0 46 98 77 30 54 7 75 10 26 32 65 3 95 
95 72 0 63
<552 bytes omitted>

答案文件(8.out

151

用户输出

151

系统信息

Exited with return code 0
测试点 #9
Accepted
得分:100
用时:14 ms
内存:2296 KiB

输入文件(9.in

15
0 90 72 64 78 25 97 16 53 98 89 29 16 52 29 
23 0 68 52 29 71 22 78 80 21 84 71 7 32 17 
32 84 0 
<565 bytes omitted>

答案文件(9.out

197

用户输出

197

系统信息

Exited with return code 0
测试点 #10
Accepted
得分:100
用时:13 ms
内存:2304 KiB

输入文件(10.in

15
0 16 92 13 100 64 47 7 63 5 97 5 35 1 94 
39 0 65 6 23 97 10 69 70 64 51 1 74 36 53 
35 95 0 59 6
<560 bytes omitted>

答案文件(10.out

224

用户输出

224

系统信息

Exited with return code 0