USACO 2017 FEB Gold visitfj 最短路

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

const int maxn = 105;
const int INF = 0x3fffffff;
int n, t, w[maxn][maxn];
struct Node
{
    int x, y, z;
    Node (int x = 0, int y = 0, int z = 0):
        x(x), y(y), z(z) {}
};
queue <Node> q;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int dis[maxn][maxn][3];
bool vis[maxn][maxn][3];

int main()
{
    freopen("visitfj.in", "r", stdin);
    freopen("visitfj.out", "w", stdout);
    scanf("%d %d", &n, &t);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &w[i][j]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 0; k < 3; ++k)
                dis[i][j][k] = INF, vis[i][j][k] = false;
    dis[1][1][0] = 0;
    vis[1][1][0] = true;
    q.push(Node(1, 1, 0));
    while (!q.empty())
    {
        Node now = q.front();
        vis[now.x][now.y][now.z] = false;
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            int x = now.x+dx[i], y = now.y+dy[i], z = (now.z+1)%3;
            if (x < 1 || y < 1 || x > n || y > n)
                continue ;
            if (dis[x][y][z] > dis[now.x][now.y][now.z]+t+((z == 0) ? w[x][y] : 0))
            {
                dis[x][y][z] = dis[now.x][now.y][now.z]+t+((z == 0) ? w[x][y] : 0);
                if (!vis[x][y][z])
                    vis[x][y][z] = true, q.push(Node(x, y, z));
            }
        }
    }
    printf("%d\n", min(dis[n][n][0], min(dis[n][n][1], dis[n][n][2])));
    return 0;
}