神解法

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
#define MAXM 4000005
#define MAXN 505
struct node{
int to,w;
bool operator<(const node &a) const{
return w>a.w;
}
};
vector<node> v[MAXM];
int n,s,t,id[MAXN][MAXN],d[MAXM];
bool vis[MAXM];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=x10+ch-48;
ch=getchar();
}
return xf;
}
int dij(){
memset(d,0x3f,sizeof(d));
d[s]=0;
priority_queue<node> q;
q.push(node{s,0});
while(q.size()){
node nd=q.top();
q.pop();
int x=nd.to;
if(vis[x]) continue;
vis[x]=1;
for(int i=0;i<v[x].size();i++){
int y=v[x][i].to;
if(d[y]>d[x]+v[x][i].w){
d[y]=d[x]+v[x][i].w;
q.push(node{y,d[y]});
}
}
}
return d[t];
}
int main(){
n=read();
n++;
s=nn+1;
t=nn+2;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
id[i][j]=(i-1)*n+j;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<n;j++){
int x;
x=read();
if(i1) v[s].push_back(node{id[i][j],x});
else if(in) v[id[i-1][j]].push_back(node{t,x});
else v[id[i-1][j]].push_back(node{id[i][j],x});
}
}
for(int i=1;i<n;i++){
for(int j=1;j<=n;j++){
int x;
x=read();
if(j1) v[id[i][j]].push_back(node{t,x});
else if(jn) v[s].push_back(node{id[i][j-1],x});
else v[id[i][j]].push_back(node{id[i][j-1],x});
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<n;j++){
int x;
x=read();
if(i1) v[id[i][j]].push_back(node{s,x});
else if(in) v[t].push_back(node{id[i-1][j],x});
else v[id[i][j]].push_back(node{id[i-1][j],x});
}
}
for(int i=1;i<n;i++){
for(int j=1;j<=n;j++){
int x;
x=read();
if(j1) v[t].push_back(node{id[i][j],x});
else if(jn) v[id[i][j-1]].push_back(node{s,x});
else v[id[i][j-1]].push_back(node{id[i][j],x});
}
}
cout<<dij();
return 0;
}