|
;
int dis[N],vis[N];
int dij() {
memset(dis,0x3f,sizeof(dis));
q.push(make_pair(0,S));
dis[S] = 0;
for(int i = 1;i <= T;++i) {
if(q.empty()) break;
pi k = q.top();
while(vis[k.second] && !q.empty()) k = q.top(),q.pop();
int u = k.second;
if(vis[u]) break;
vis[u] = 1;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
if(vis[v]) continue;
if(dis[v] > dis[u] + e[i].w) {
dis[v] = dis[u] + e[i].w;
q.push(make_pair(dis[v],v));
}
}
}
return dis[T];
}
int main() {
int n = read();
int now;
S = n * n + 1,T = S + 1;
now = 1;
for(int i = 1;i <= n + 1;++i) {
for(int j = 1;j <= n;++j,++now) {
int w = read();
if(i == 1) add(now,T,w);
else if(i == n + 1) add(S,now - n,w);
else add(now,now - n,w);
}
}
now = 1;
for(int i = 1;i <= n;++i) {
for(int j = 1;j <= n + 1;++j,++now) {
int w = read();
if(j == 1) add(S,now,w);
else if(j == n + 1) add(--now,T,w);
else add(now - 1,now,w);
}
}
now = 1;
for(int i = 1;i <= n + 1;++i) {
for(int j = 1;j <= n;++j,++now) {
int w = read();
if(i == 1 ||i == n + 1) continue;
add(now - n,now,w);
}
}
now = 1;
for(int i = 1;i <= n;++i) {
for(int j = 1;j <= n + 1;++j,++now) {
int w = read();
if(j == 1 || j == n + 1) continue;
add(now,now - 1,w);
}
--now;
}
cout<<dij();
return 0;
}
|