用户输出
113
系统信息
Exited with return code 0
编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#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;
}
用户输出
113
系统信息
Exited with return code 0
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>
用户输出
144
系统信息
Exited with return code 0
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>
用户输出
135
系统信息
Exited with return code 0
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>
用户输出
131
系统信息
Exited with return code 0
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>
用户输出
166
系统信息
Exited with return code 0
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>
用户输出
93
系统信息
Exited with return code 0
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>
用户输出
167
系统信息
Exited with return code 0
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>
用户输出
151
系统信息
Exited with return code 0
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>
用户输出
197
系统信息
Exited with return code 0