| 比赛 |
!信心赛 |
评测结果 |
AATTTTTTTT |
| 题目名称 |
海拔 |
最终得分 |
20 |
| 用户昵称 |
LikableP |
运行时间 |
16.820 s |
| 代码语言 |
C++ |
内存使用 |
7.56 MiB |
| 提交时间 |
2026-01-17 11:24:05 |
显示代码纯文本
#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long ll;
struct EDGE {
int u, v, w;
};
int n;
std::vector<EDGE> edge;
int PointToNum(int x, int y) {
return (x - 1) * (n + 1) + y;
}
void AddEdge(int u, int v, int w) {
edge.push_back({u, v, w});
}
int h[251010];
ll ans = 0x7fffffffffffffff;
void check() {
ll sum = 0;
for (auto [u, v, w] : edge) {
if (h[u] < h[v]) sum += w;
}
ans = std::min(ans, sum);
}
void dfs(int now) {
if (now > (n + 1) * (n + 1) - 1) {
check();
return ;
}
h[now] = 0;
dfs(now + 1);
h[now] = 1;
dfs(now + 1);
}
int main() {
#ifdef LOCAL
freopen("!input.in", "r", stdin);
freopen("!output.out", "w", stdout);
#else
freopen("altitude.in", "r", stdin);
freopen("altitude.out", "w", stdout);
#endif
scanf("%d", &n);
for (int i = 1; i <= n + 1; ++i) {
for (int j = 1, w; j <= n; ++j) {
scanf("%d", &w);
AddEdge(PointToNum(i, j), PointToNum(i, j + 1), w);
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1, w; j <= n + 1; ++j) {
scanf("%d", &w);
AddEdge(PointToNum(i, j), PointToNum(i + 1, j), w);
}
}
for (int i = 1; i <= n + 1; ++i) {
for (int j = 2, w; j <= n + 1; ++j) {
scanf("%d", &w);
AddEdge(PointToNum(i, j), PointToNum(i, j - 1), w);
}
}
for (int i = 2; i <= n + 1; ++i) {
for (int j = 1, w; j <= n + 1; ++j) {
scanf("%d", &w);
AddEdge(PointToNum(i, j), PointToNum(i - 1, j), w);
}
}
h[1] = 0;
h[(n + 1) * (n + 1)] = 1;
dfs(2);
printf("%lld\n", ans);
return 0;
}