Description
给出一个N*M的网格图，有一些方格里面存在城市，其中首都位于网格图的左上角。你可以沿着网络的边界走，要求你走的路线是一个环并且所有城市都要被你走出来的环圈起来，即想从方格图的外面走到任意一个城市一定要和你走的路线相交。你沿着方格的边界走是需要费用的，不同的边界费用可能不同，求最小代价。
1<=N,M<=400,走过边界的代价为正整数且不超过10^9
Input
Output
Sample Input
Input 1
3 3
1 0 0
1 0 0
0 0 1
1 4 9 4
1 6 6 6
1 2 2 9
1 1 1
4 4 4
2 4 2
6 6 6
input 2
3 3
1 0 1
0 0 0
0 1 0
2 1 1 3
5 6 1 1
2 1 1 3
2 1 1
3 4 1
4 1 1
5 1 2
3 3
1 0 0
1 0 0
0 0 1
1 4 9 4
1 6 6 6
1 2 2 9
1 1 1
4 4 4
2 4 2
6 6 6
input 2
3 3
1 0 1
0 0 0
0 1 0
2 1 1 3
5 6 1 1
2 1 1 3
2 1 1
3 4 1
4 1 1
5 1 2
Sample Output
output 1
38
output 2
22
38
output 2
22
HINT
Source
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~最短路+思路~
对于每个标记的格子我们跑从左上角到它的最短路，记录下路径。
可以证明，最终的路径一定在这些最短路的最外面，即它包含这些最短路和所有标记的格子。
对于每个点，我们都把它拆成四个，原来的边上下两对分别连边，最短路之间连inf的边，除1号点外每个点的四个点互相连边。从1号点的2号向4号跑最短路即可。
这题卡SPFA；N和M必须用const int，否则会RE。所以还是少用define比较好啊QwQ
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
#define d(u,v) ((u-1)*(m+1)+v)
#define dd(u,v,k) ((d(u,v)-1)*4+k+1)
#define pa pair<ll,int>
#define mp make_pairconst int N=402*402*4+5;
const int M=N*4;int n,m,fi[N],w[M],ne[M],v[M],cnt,a[405][405],b[405][405],c[405][405],pre[N],tot;
ll dis[N];
bool vis[N],mark[N][4],del[N];priority_queue<pa,vector<pa>,greater<pa> > q;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<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}void add(int u,int vv,int val)
{if(del[u] || del[vv]) return;w[++cnt]=vv;ne[cnt]=fi[u];fi[u]=cnt;v[cnt]=val;w[++cnt]=u;ne[cnt]=fi[vv];fi[vv]=cnt;v[cnt]=val;
}void dij(int s)
{for(int i=1;i<=tot;i++) dis[i]=1ll<<60,pre[i]=0;q.push(mp(0,s));dis[s]=0;while(!q.empty()){pa k=q.top();q.pop();int now=k.second;if(dis[k.second]!=k.first) continue;for(int i=fi[now];i;i=ne[i])if(dis[w[i]]>dis[now]+v[i]){dis[w[i]]=dis[now]+v[i];pre[w[i]]=now;q.push(mp(dis[w[i]],w[i]));}}
}void dfs(int u)
{if(u==1 || vis[u]) return;vis[u]=1;if(pre[u]==u-1) mark[u][3]=mark[pre[u]][1]=1;if(pre[u]==u+1) mark[u][1]=mark[pre[u]][3]=1;if(pre[u]==u-m-1) mark[u][0]=mark[pre[u]][2]=1;if(pre[u]==u+m+1) mark[u][2]=mark[pre[u]][0]=1;dfs(pre[u]);
}int main()
{n=read();m=read();tot=(n+1)*(m+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) a[i][j]=read();for(int i=1;i<=n;i++)for(int j=1;j<=m+1;j++) b[i][j]=read(),add(d(i,j),d(i+1,j),b[i][j]);for(int i=1;i<=n+1;i++)for(int j=1;j<=m;j++) c[i][j]=read(),add(d(i,j),d(i,j+1),c[i][j]);dij(1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) if(a[i][j]) dfs(d(i,j));for(int i=1;i<=tot;i++) fi[i]=0;cnt=0;del[1]=1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]) del[dd(i,j,2)]=del[dd(i+1,j,1)]=del[dd(i,j+1,3)]=del[dd(i+1,j+1,0)]=1; for(int i=1;i<=n+1;i++)for(int j=1;j<=m+1;j++)for(int k=0;k<4;k++) if(!mark[d(i,j)][k]) add(dd(i,j,k),dd(i,j,(k+1)%4),0);for(int i=1;i<=n;i++)for(int j=1;j<=m+1;j++) add(dd(i,j,3),dd(i+1,j,0),b[i][j]),add(dd(i,j,2),dd(i+1,j,1),b[i][j]);for(int i=1;i<=n+1;i++)for(int j=1;j<=m;j++) add(dd(i,j,1),dd(i,j+1,0),c[i][j]),add(dd(i,j,2),dd(i,j+1,3),c[i][j]);tot<<=2;dij(2);printf("%lld\n",dis[4]);return 0;
}