。。和HDU3870类似。。注意n=1和m=1的情况。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define INF (1<<30)
#define MAXN 2800000
struct Edge{
int v,w,next;
}edge[MAXN<<];
int vs,vt,NV,NE,head[MAXN];
void addEdge(int u,int v,int w){
edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u];
head[u]=NE++;
}
struct Node{
int u,d;
Node(int _u=,int _d=):u(_u),d(_d){}
bool operator<(const Node &nd)const{
return nd.d<d;
}
};
int d[MAXN];
bool vis[MAXN];
int dijkstra(){
for(int i=; i<NV; ++i){
d[i]=INF; vis[i]=;
}
d[vs]=;
priority_queue<Node> que;
que.push(Node(vs,));
while(!que.empty()){
Node nd=que.top(); que.pop();
if(nd.u==vt) return nd.d;
if(vis[nd.u]) continue;
vis[nd.u]=;
for(int i=head[nd.u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(vis[v]) continue;
if(d[v]>d[nd.u]+edge[i].w){
d[v]=d[nd.u]+edge[i].w;
que.push(Node(v,d[v]));
}
}
}
return INF;
}
int main(){
int n,m,a;
scanf("%d%d",&n,&m);
if(n== && m==){
puts("");
return ;
}
vs=(n-)*(m-)*; vt=vs+; NV=vt+; NE=;
memset(head,-,sizeof(head));
int mm=INF;
for(int i=; i<n; ++i){
for(int j=; j<m-; ++j){
scanf("%d",&a);
mm=min(mm,a);
if(i==) addEdge(i*(m-)+j,vt,a);
if(i==n-) addEdge(vs,(i-)*(m-)+j+(n-)*(m-),a);
if(i!= && i!=n-){
addEdge(i*(m-)+j,(i-)*(m-)+j+(n-)*(m-),a);
addEdge((i-)*(m-)+j+(n-)*(m-),i*(m-)+j,a);
}
}
}
for(int i=; i<n-; ++i){
for(int j=; j<m; ++j){
scanf("%d",&a);
mm=min(mm,a);
if(j==) addEdge(vs,i*(m-)+j+(n-)*(m-),a);
if(j==m-) addEdge(i*(m-)+j-,vt,a);
if(j!= && j!=m-){
addEdge(i*(m-)+j+(n-)*(m-),i*(m-)+j-,a);
addEdge(i*(m-)+j-,i*(m-)+j+(n-)*(m-),a);
}
}
}
for(int i=; i<n-; ++i){
for(int j=; j<m-; ++j){
scanf("%d",&a);
mm=min(mm,a);
addEdge(i*(m-)+j,i*(m-)+j+(n-)*(m-),a);
addEdge(i*(m-)+j+(n-)*(m-),i*(m-)+j,a);
}
}
if(n== || m==) printf("%d",mm);
else printf("%d",dijkstra());
return ;
}