比赛 !信心赛 评测结果 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;
}