BZOJ-4992: [Usaco2017 Feb]Why Did the Cow Cross the Road

Description

有一幅n*n的方格图，n <=100，每个点上有一个值。从（1,1）出发，走到（n,n），只能走上下左右。每走一步花费t，每走三步需要花费走完三步后到达格子的值。求最小花费的值。

本来好像就是搜索。。。
闲得写了个类似分层图最短路的spfa。拿了rank1，233。
dp[x][y][z]表示(x,y)点，是第z步的最短路，spfa。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[105][105][3],map[105][105],n,t;
bool v[105][105][3];
struct node {
    int x,y,z;
};
queue<node>q;
void spfa()
{
    memset(dp,0x3f,sizeof dp);
    dp[1][1][0]=0; q.push((node){1,1,0});
    int x,y,z,dis; v[1][1][0]=1;
    while(!q.empty())
    {
        x=q.front().x; y=q.front().y; z=q.front().z; q.pop();
        dis=dp[x][y][z]; v[x][y][z]=0;
        if(z==2)
        {
            if(x!=1&&dp[x-1][y][0]>dis+t+map[x-1][y])
            {
                dp[x-1][y][0]=dis+t+map[x-1][y];
                if(!v[x-1][y][0]) q.push((node){x-1,y,0}),v[x-1][y][0]=1;
            }
            if(x!=n&&dp[x+1][y][0]>dis+t+map[x+1][y])
            {
                dp[x+1][y][0]=dis+t+map[x+1][y];
                if(!v[x+1][y][0]) q.push((node){x+1,y,0}),v[x+1][y][0]=1;
            }
            if(y!=1&&dp[x][y-1][0]>dis+t+map[x][y-1])
            {
                dp[x][y-1][0]=dis+t+map[x][y-1];
                if(!v[x][y-1][0]) q.push((node){x,y-1,0}),v[x][y-1][0]=1;
            }
            if(y!=n&&dp[x][y+1][0]>dis+t+map[x][y+1])
            {
                dp[x][y+1][0]=dis+t+map[x][y+1];
                if(!v[x][y+1][0]) q.push((node){x,y+1,0}),v[x][y+1][0]=1;
            }
        }
        else
        {
            dis+=t; z++;
            if(x!=1&&dp[x-1][y][z]>dis)
            {
                dp[x-1][y][z]=dis;
                if(!v[x-1][y][z]) q.push((node){x-1,y,z}),v[x-1][y][z]=1;
            }
            if(x!=n&&dp[x+1][y][z]>dis)
            {
                dp[x+1][y][z]=dis;
                if(!v[x+1][y][z]) q.push((node){x+1,y,z}),v[x+1][y][z]=1;
            }
            if(y!=1&&dp[x][y-1][z]>dis)
            {
                dp[x][y-1][z]=dis;
                if(!v[x][y-1][z]) q.push((node){x,y-1,z}),v[x][y-1][z]=1;
            }
            if(y!=n&&dp[x][y+1][z]>dis)
            {
                dp[x][y+1][z]=dis;
                if(!v[x][y+1][z]) q.push((node){x,y+1,z}),v[x][y+1][z]=1;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&map[i][j]);
    spfa();
    printf("%d",min(dp[n][n][0],min(dp[n][n][1],dp[n][n][2])));
    return 0;
}