1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 2000000000 using namespace std; typedef long long ll; int (){ int f=1,x=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return f*x; } struct Edge{ int v,cost,_next; }; Edge edge[7000005]; int cnt=0,at[2000005],n,m,S,T,sq,d[2010005]; int que[7000005]; bool in[2000005]={0}; int id(int i,int j){return (i-1)*(m-1)+j;} void addedge(int _u,int _v,int _cost){ edge[++cnt].v=_v, edge[cnt].cost=_cost, edge[cnt]._next=at[_u], at[_u]=cnt; edge[++cnt].v=_u, edge[cnt].cost=_cost, edge[cnt]._next=at[_v], at[_v]=cnt; } void spfa_bfs(){ fill(d+1,d+sq*2+10000,INF); int i,_u,_v,_co,r=0,f=0,qc=0; d[S]=0,que[r++]=S,in[S]=1,qc++; while(qc&&qc<=7000000){ _u=que[f],in[_u]=0; f=(f==7000000)?0:f+1; qc--; for(i=at[_u];i;i=edge[i]._next){ _v=edge[i].v,_co=edge[i].cost; if(d[_u]+_co<d[_v]){ d[_v]=d[_u]+_co; if(!in[_v]){ in[_v]=1,que[r]=_v; r=(r==7000000)?0:r+1; qc++; } } } } } void init(){ n=read(),m=read(),sq=(n-1)*(m-1); if(n==1||m==1){ int ans=INF,c; for(int i=1;i<=m+n-2;i++) c=read(),ans=min(ans,c); printf("%dn",ans); return ; } S=2*sq+1,T=2*sq+2; int u,v,c; for(int i=1;i<=n;i++) for(int j=1;j<m;j++){ c=read(); if(i==1)addedge(id(i,j),T,c); else if(i==n)addedge(id(i-1,j)+sq,S,c); else addedge(id(i-1,j)+sq,id(i,j),c); } for(int i=1;i<n;i++) for(int j=1;j<=m;j++){ c=read(); if(j==1)addedge(id(i,j)+sq,S,c); else if(j==m)addedge(id(i,j-1),T,c); else addedge(id(i,j-1),id(i,j)+sq,c); } for(int i=1;i<n;i++) for(int j=1;j<m;j++){ c=read(); addedge(id(i,j),id(i,j)+sq,c); } spfa_bfs(); printf("%dn",d[T]); } void solve(){ } int main(){ init(); solve(); return 0; }
|
近期评论