【题目链接】
【算法】
dist[i][j][k]表示当前走到(i,j)，走的步数除以3的余数为k的最小花费
spfa即可
【代码】
#include<bits/stdc++.h> using namespace std; #define MAXN 110 const int INF = 1e9; struct info { int x,y,s; }; const int dx[4] = {0,0,-1,1}; const int dy[4] = {-1,1,0,0}; int i,j,n,t; int val[MAXN][MAXN]; template <typename T> inline void read(T &x) { int f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; } for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) write(x/10); putchar(x%10+'0'); } template <typename T> inline void writeln(T x) { write(x); puts(""); } bool ok(int x,int y) { return x >= 1 && x <= n && y >= 1 && y <= n; } inline void spfa() { int i,j,tx,ty,ans; queue< info > q; static int dist[MAXN][MAXN][3],inq[MAXN][MAXN][3]; info cur; for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { dist[i][j][0] = dist[i][j][1] = dist[i][j][2] = INF; } } dist[1][1][0] = 0; inq[1][1][0] = 1; q.push((info){1,1,0}); while (!q.empty()) { cur = q.front(); inq[cur.x][cur.y][cur.s] = 0; q.pop(); for (i = 0; i < 4; i++) { tx = cur.x + dx[i]; ty = cur.y + dy[i]; if (ok(tx,ty)) { if (!cur.s) { if (dist[cur.x][cur.y][0] + t < dist[tx][ty][1]) { dist[tx][ty][1] = dist[cur.x][cur.y][0] + t; if (!inq[tx][ty][1]) { inq[tx][ty][1] = 1; q.push((info){tx,ty,1}); } } } if (cur.s == 1) { if (dist[cur.x][cur.y][1] + t < dist[tx][ty][2]) { dist[tx][ty][2] = dist[cur.x][cur.y][1] + t; if (!inq[tx][ty][2]) { inq[tx][ty][2] = 1; q.push((info){tx,ty,2}); } } } if (cur.s == 2) { if (dist[cur.x][cur.y][2] + val[tx][ty] + t < dist[tx][ty][0]) { dist[tx][ty][0] = dist[cur.x][cur.y][2] + val[tx][ty] + t; if (!inq[tx][ty][0]) { inq[tx][ty][0] = 1; q.push((info){tx,ty,0}); } } } } } } ans = min(min(dist[n][n][0],dist[n][n][1]),dist[n][n][2]); writeln(ans); } int main() { read(n); read(t); for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { read(val[i][j]); } } spfa(); return 0; }