【题目分析】

    可以知道，所有的海拔是0或1

    最小割转最短路，就可以啦

    SPFA被卡，只能换DIJ

【代码】

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define maxn 2000005int h[maxn],to[maxn],ne[maxn],w[maxn],en=0;int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}    while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}int dis[maxn];struct cmp{    bool operator () (const int &a,const int &b)    {return dis[a]>dis[b];}};struct Table{    int h[maxn],ne[maxn],to[maxn],w[maxn],vis[maxn];    priority_queue 
          
           
            ,cmp> q; int en; void init() { memset(h,-1,sizeof h); en=0; while (!q.empty()) q.pop(); } void add(int a,int b,int c) { ne[en]=h[a]; to[en]=b; w[en]=c; h[a]=en++; } void dij(int s) { memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); dis[s]=0; q.push(s); vis[s]=1; while (!q.empty()) { int x=q.top(); q.pop(); vis[x]=0; for (int i=h[x];i>=0;i=ne[i]) { if (dis[to[i]]>dis[x]+w[i]) { dis[to[i]]=dis[x]+w[i]; if (!vis[to[i]]) { vis[to[i]]=1; q.push(to[i]); } } } } }}map;void add(int a,int b,int c){ to[en]=b; ne[en]=h[a]; w[en]=c; h[a]=en++;}int n,S=0,T=maxn-1;int hash[605][605],cnt=0;int inq[maxn];void SPFA(){ queue 
            
              q; memset(dis,0x3f,sizeof dis); while (!q.empty()) q.pop(); q.push(S); inq[S]=1; dis[S]=0; while (!q.empty()) { int x=q.front(); q.pop(); inq[x]=0; for (int i=h[x];i>=0;i=ne[i]) { if (dis[to[i]]>dis[x]+w[i]) { dis[to[i]]=dis[x]+w[i]; if (!inq[to[i]]) { inq[to[i]]=1; q.push(to[i]); } } } } printf("%d\n",dis[T]);}int main(){ map.init(); memset(h,-1,sizeof h); n=read(); for (int i=0;i<=n+1;++i) for (int j=0;j<=n+1;++j) hash[i][j]=++cnt; for (int i=0;i<=n+1;++i) hash[0][i]=maxn-1; for (int i=0;i<=n+1;++i) hash[n+1][i]=0; for (int i=0;i<=n+1;++i) hash[i][0]=0; for (int i=0;i<=n+1;++i) hash[i][n+1]=maxn-1; for (int i=1;i<=n+1;++i) for (int j=1;j<=n;++j) { int tmp=read(); map.add(hash[i][j],hash[i-1][j],tmp); } for (int i=1;i<=n;++i) for (int j=1;j<=n+1;++j) { int tmp=read(); map.add(hash[i][j-1],hash[i][j],tmp); } for (int i=1;i<=n+1;++i) for (int j=1;j<=n;++j) { int tmp=read(); map.add(hash[i-1][j],hash[i][j],tmp); } for (int i=1;i<=n;++i) for (int j=1;j<=n+1;++j) { int tmp=read(); map.add(hash[i][j],hash[i][j-1],tmp); } map.dij(S); printf("%d\n",dis[T]);}