题目大意

一个四周有围墙的正方形操场被南北方向和东西方向各划了 $N-1$ 条白线，分成了一个 $N\times N$ 的网格（$3\leq N\leq 100$）。小明在网格的左上角，安博士在网格的右下角。现在小明从自己的位置出发，目的是去安博士那里。小明从一个网格走到相邻的网格需要小心翼翼的跨过白线，不能把白线踩坏，每跨过一条白线都需要 $T$ 个单位时间（$0\leq T\leq 1,000,000$）。另外小明每走过3块网格（不包括小明初始的位置网格，但如果到达终点时如果符合“每走过 $3$ 块网格”的条件则需要把终点休息的时间加上）就需要休息一下，休息也需要时间。

那么小明到达安博士那里的最短时间是多少？

输入

输入第 $1$ 行 $2$ 个整数 $N$ 和 $T$ 。

接下来是一个 $N\times N$ 的矩阵，表示小明如果在网格停留，需要停留的时间。

输出

输出一个整数表示答案。

我的思路：

枚举从当前点走三步可到达的 $16$ 个点并连边，从(1,1)到(n,n)做最短路。

代码

#include<bits/stdc++.h>
#pragma G++ optimize(2)
using namespace std;

#define PII pair<int,int>

int n,t;
int a[105][105];
int num_edge;
struct node{
	int to;
	int nxt;
	int w;
}edge[500005];
int head[105];
int dis[105];
int vis[105];
int ans;
int dx[20]={0,-3,-2,-1,0,1,2,3,2,1,0,-1,-2,-1,0,1,0};
int dy[20]={0,0,-1,-2,-3,-2,-1,0,1,2,3,2,1,0,1,0,-1};

int zip(int u,int v){
	return (u-1)*n+v;
}

void add(int u,int v,int w){
	edge[++num_edge].w=w;
	edge[num_edge].to=v;
	edge[num_edge].nxt=head[u];
	head[u]=num_edge;
	return;
}

void Add(int u,int v){
	for(int i=1;i<=16;i++){
		int sx=u+dx[i];
		int sy=v+dy[i];
		if(sx>=1&&sx<=n&&sy>=1&&sy<=n)
			add(zip(u,v),zip(sx,sy),3*t+a[sx][sy]);
	}
}

void Dijkstra(){
	priority_queue<PII,vector<PII>,greater<PII> > pq;
	pq.push((PII){
		0,1
	});
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    while(!pq.empty()){
		int su=pq.top().second;
        pq.pop();
        if(vis[su])
        	continue;
        vis[su]=1;
        for(int i=head[su];i;i=edge[i].nxt){
            int sv=edge[i].to;
            if(dis[sv]>dis[su]+edge[i].w){
				dis[sv]=dis[su]+edge[i].w;
                pq.push((PII){
					dis[sv],sv
				});
            }
        }
    }
    return;
}

signed main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>t;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			Add(i,j);
	Dijkstra();
	ans=dis[zip(n,n)];
	cout<<dis[zip(n,n)]<<endl;
	ans=min(ans,zip(n-1,n)+t);
	ans=min(ans,zip(n,n-1)+t);
	ans=min(ans,zip(n-2,n)+2*t);
	ans=min(ans,zip(n-1,n-1)+2*t);
	ans=min(ans,zip(n,n-2)+2*t);
	cout<<ans;
	return 0;
}