题解 P3659 【[USACO17FEB]Why Did the Cow Cross the Road I G】

· · 题解

没看见有SPFA的题解，那我就来一发吧！

我们对于每一个位置，将他们与自己走三步的点进行连边，边的权值为t*3+到达的点的权值。如图所示（注意它可以向上再向下再向上这类的情况，所以有16个方向）：

随后，从起点(1,1)跑一遍SPFA，最后统计答案分别从(n,n),(n-1,n),(n,n-1),(n-2,n),(n,n-2),(n-1,n-1)中转移过来。具体看代码。

由于本题边的构造可以发现很难卡SPFA，SPFA没有死，而且就算卡了复杂度也可以接受QWQ

#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N=105;
inline int read(){//快读
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int cnt,fir[N*N],nxt[N*N*16],go[N*N*16],val[N*N*16];//邻接表存边
int n,t,a[N][N];
long long ans,d[N*N];
bool vis[N*N];
int h(int x,int y)//给每个点设立一个编号
{
    return (x-1)*n+y;   
}
inline void Add(int u,int v,int w)
{
    nxt[++cnt]=fir[u];  
    fir[u]=cnt;
    go[cnt]=v;
    val[cnt]=w;
}//连边
const int dx[16]={-2,-1,1,2,2,1,-1,-2,0,1,0,-1,0,3,0,-3};
const int dy[16]={1,2,2,1,-1,-2,-2,-1,1,0,-1,0,3,0,-3,0};//枚举16个方向

inline void COCO_made_me_Do_it(int x,int y)
{
    for(int i=0;i<16;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];  
        if(xx>0&&xx<=n&&yy>0&&yy<=n)//判断是否越界
        {
            Add(h(x,y),h(xx,yy),a[xx][yy]+3*t);//建边；
        }   
    }
}
queue<int> q;
void SPFA(int x,int y)//SPFA跑最短路
{
    memset(vis,false,sizeof(vis));
    memset(d,0x3f,sizeof(d));
    d[h(x,y)]=0;
    vis[h(x,y)]=true;
    q.push(h(x,y));
    while(!q.empty())
    {
        int xx=q.front();q.pop();
        vis[xx]=false;
        for(int e=fir[xx];e;e=nxt[e])
        {
            int yy=go[e];
            if(d[xx]+val[e]<d[yy])
            {
                d[yy]=d[xx]+val[e]; 
                if(!vis[yy])
                {
                    vis[yy]=true;q.push(yy);
                }
            }
        }   
    }
}
int main()
{
    n=read();t=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            COCO_made_me_Do_it(i,j);
    SPFA(1,1);
    ans=0x7fffffff;
    ans=min(ans,d[h(n,n)]);
    if(n>=2)ans=min(ans,d[h(n,n-1)]+t);
    if(n>=2)ans=min(ans,d[h(n-1,n)]+t);
    if(n>=3)ans=min(ans,d[h(n-2,n)]+2*t);
    if(n>=3)ans=min(ans,d[h(n,n-2)]+2*t);
    if(n>=2)ans=min(ans,d[h(n-1,n-1)]+2*t);//没什么意义的特判，更新答案
    printf("%lld\n",ans);
    return 0;
}