[USACO17FEB]Why Did the Cow Cross the Road I G

一开始想写$DP$，发现直接转移完全有后效性

所以本小蒟蒻写了个最短路

每走三步就要吃草是这个题最难搞的地方，我们建图时不妨只对于距离等于三的点连边

考虑完全覆盖所有情况，从一个点走一步，两步，然后三步，和直接走三步代价是等价的

这样从每个点到与其曼哈顿距离为三的所有点连边即可

考虑到终点的答案，对于所有小于三步到终点的位置到终点的代价，找到最小值即为答案

有个坑就是比如右左右这种走法，我们也需要从一个点向其周围的点连边

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define int long long

using namespace std;

const int maxn=;

struct edge{

    int next,to,dis;

}e[*maxn];

int n,t,g[][],len[maxn],head[maxn],cnt,ans=1e9;

int dx[]={-,-,-,-,-,,,,,,,,,,,-};

int dy[]={-,-,,,,-,-,-,,,,,,,-,};

bool exist[maxn];

inline void add(int x,int y,int d)

{

    e[++cnt].next=head[x];

    e[cnt].to=y;

    e[cnt].dis=d;

    head[x]=cnt;

}

inline int make(int x,int y)

{

    return x*n+y;

}

int dijkstra()

{

    priority_queue<pair<int,int> >q;

    memset(len,0x3f,sizeof(len));

    q.push(make_pair(,make(,)));

    len[make(,)]=;

    while(!q.empty())

    {

        int u=q.top().second;

        q.pop();

        if(exist[u])

            continue;

        exist[u]=;

        for(int v,i=head[u];i;i=e[i].next)

            if(len[v=e[i].to]>len[u]+e[i].dis)

            {

                len[v]=len[u]+e[i].dis;

                q.push(make_pair(-len[v],v));

            }

    }

}

void check(int x,int y)

{

    for(int i=;i<;i++)

        if(x+dx[i]>&&x+dx[i]<=n&&y+dy[i]>&&y+dy[i]<=n)

            add(make(x,y),make(x+dx[i],y+dy[i]),*t+g[x+dx[i]][y+dy[i]]);

}

signed main()

{

    scanf("%lld%lld",&n,&t);

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

        for(int j=;j<=n;j++)

            scanf("%lld",&g[i][j]);

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

        for(int j=;j<=n;j++)

            check(i,j);

    dijkstra();

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

        for(int j=;j<=n;j++)

            if(*n-i-j<)

                ans=min(ans,len[make(i,j)]+(*n-i-j)*t);

    printf("%lld\n",ans);

    return ;

}