记录编号	605066	评测结果	AAAAAA
题目名称	752.[BJOI2006] 狼抓兔子	最终得分	100
用户昵称	彭欣越	是否通过	通过
代码语言	C++	运行时间	0.450 s
提交时间	2025-08-13 15:59:19	内存使用	41.37 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2010;
//int dx[]={0,-1,1,0,1,-1},dy[]={1,0,0,-1,1,-1};
ll ans=1e18+10;
int n,m,ed;
int dis[N*N],vis[N*N];
int tot,head[N*N];
struct edge {
	int u,v,w,nxt,x;
}e[2*N*N];
void add (int u,int v,int w) {
	e[++tot].v=v;
	e[tot].u=u;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
}
priority_queue<pair<int,int>>q;
void dijkstra () {
	memset(dis,0x3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[0]=0;
	q.push(make_pair(0,0));
	while (!q.empty()) {
		int x=q.top().second;
		q.pop();
		if (vis[x]) continue;
		vis[x]=1;
		for (int i=head[x];i;i=e[i].nxt) {
			int v=e[i].v,w=e[i].w;
			if (dis[v]>dis[x]+w) {
				dis[v]=dis[x]+w;
				if (!vis[v]) q.push(make_pair(-dis[v],v));
			}
		} 
	}
}
int main () {
	freopen("bjrabbit.in","r",stdin);
	freopen("bjrabbit.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	ed=(2*n-2)*(m-1)+1;
	int x;
	for (int i=1;i<m;i++) {
		cin >> x;
		add(i*2,ed,x);
	}
	for (int i=2;i<n;i++) {
		for (int j=1;j<m;j++) {
			cin >> x;
			add(2*(i-2)*(m-1)-1+2*j,2*(i-1)*(m-1)+2*j,x);
			add(2*(i-1)*(m-1)+2*j,2*(i-2)*(m-1)-1+2*j,x);
		}
	}
	for (int i=1;i<m;i++) {
		cin >> x;
		add(0,2*(n-2)*(m-1)-1+2*i,x);
	}
	for (int i=1;i<n;i++) {
		for (int j=1;j<=m;j++) {
			int x;
			cin >> x;
			if (j==1) add(0,2*(i-1)*(m-1)-1+2*j,x);
			else if (j==m) add(2*(i-1)*(m-1)-2+2*j,ed,x);
			else {
				add(2*(i-1)*(m-1)-1+2*j,2*(i-1)*(m-1)-2+2*j,x);
				add(2*(i-1)*(m-1)-2+2*j,2*(i-1)*(m-1)-1+2*j,x);
			}
		}
	}
	for (int i=1;i<n;i++) {
		for (int j=1;j<m;j++) {
			int x;
			cin >> x;
			add(2*(i-1)*(m-1)-1+2*j,2*(i-1)*(m-1)+2*j,x);
			add(2*(i-1)*(m-1)+2*j,2*(i-1)*(m-1)-1+2*j,x);
		}
	}
	dijkstra();
	cout << dis[ed] <<endl;
	return 0;
}