Luogu2295 MICE

Lougu2295 MICE

给一个 \(n\times m\) 的矩阵 \(a\) ，求一条从 \((1,\ 1)\) 到 \((n,\ m)\) 的最短路径，使得与路径相接的所有网格的权值和最小

\(n,\ m\leq10^3,\ 0\leq a_{i,j}\leq100\)

令 \(f_{0/1,\ i,\ j}\) 表示，走到 \((i,\ j)\) 时，上一步是向下走/向右走的最优值

代码

#include <bits/stdc++.h>

using namespace std;

#define nc getchar()

const int maxn = 1010;

int n, m, a[maxn][maxn], f[2][maxn][maxn];

inline int read() {

  int x = 0; char c = nc;

  while (c < 48) c = nc;

  while (c > 47) x = x * 10 + c - 48, c = nc;

  return x;

}

int main() {

  n = read(), m = read();

  for (int i = 1; i <= n; i++) {

    for (int j = 1; j <= m; j++) {

      a[i][j] = read();

    }

  }

  memset(f, 0x3f, sizeof f);

  f[0][1][1] = f[1][1][1] = a[1][1] + a[1][2] + a[2][1];

  for (int i = 1; i <= n; i++) {

    for (int j = 1; j <= m; j++) {

      if (i == 1 && j == 1) continue;

      f[0][i][j] = min(f[0][i - 1][j] + a[i][j - 1], f[1][i - 1][j]) + a[i + 1][j] + a[i][j + 1];

      f[1][i][j] = min(f[0][i][j - 1], f[1][i][j - 1] + a[i - 1][j]) + a[i + 1][j] + a[i][j + 1];

    }

  }

  printf("%d", min(f[0][n][m], f[1][n][m]));

  return 0;

}

巴特西

Luogu2295 MICE

最新文章

热门文章