1 #include
     
        2 #include
      
         3 #include
       
          4 #define inf 1000000000  5 #define M 155  6 using namespace std;  7 int xx[5]={
   0,1,-1,0,0},yy[5]={
   0,0,0,1,-1};  8 int a[M][M],b[M][M],n,m,mx,x1,x2,y1,y2,z1,z2,a1,a2,b1,b2,c1,c2,v[M][M][2*M],d[M][M][2*M];  9 char ch; 10 int ans=inf; 11 struct data 12 { 13     int x,y,w,w1; 14 }; 15 bool operator>(data a,data b) 16 { 17     return a.w>b.w; 18 } 19 void dij(int x,int y) 20 { 21     for(int i=1;i<=n;i++) 22       for(int j=1;j<=m;j++) 23         for(int k=0;k<=mx;k++) 24           { 25             v[i][j][k]=0; 26             d[i][j][k]=inf; 27           } 28     priority_queue
        
         ,greater >q; 29 v[x][y][0]=1; 30 d[x][y][a[x][y]]=b[x][y]; 31 q.push((data){x,y,b[x][y],a[x][y]}); 32 for(;!q.empty()&&(!v[x1][x2][0]||!v[y1][y2][0]||!v[z1][z2][0]);) 33 { 34 int x=q.top().x,y=q.top().y,w1=q.top().w1; 35 q.pop(); 36 if(v[x][y][w1]) 37 continue; 38 if(w1) 39 { 40 for(int i=0;i<5;i++) 41 { 42 int a1=x+xx[i],a2=y+yy[i]; 43 if(a1<1||a2<1||a1>n||a2>m||v[a1][a2][w1-1]) 44 continue; 45 if(d[x][y][w1]
           
            d[x][y][0]+b[x][y]) 54 { 55 d[x][y][a[x][y]]=d[x][y][0]+b[x][y]; 56 q.push((data){x,y,d[x][y][a[x][y]],a[x][y]}); 57 } 58 } 59 for(;!q.empty();q.pop()); 60 return; 61 } 62 int main() 63 { 64 scanf("%d%d",&n,&m); 65 mx=n+m-2; 66 for(int i=1;i<=n;i++) 67 for(int j=1;j<=m;j++) 68 { 69 scanf("%d",&a[i][j]); 70 a[i][j]=min(a[i][j],max(mx-i-j+2,i+j-2)); 71 } 72 for(int i=1;i<=n;i++) 73 for(int j=1;j<=m;j++) 74 scanf("%d",&b[i][j]); 75 scanf("%d%d%d%d%d%d",&x1,&x2,&y1,&y2,&z1,&z2); 76 dij(x1,x2); 77 a1=d[y1][y2][0]; 78 a2=d[z1][z2][0]; 79 dij(y1,y2); 80 b1=d[x1][x2][0]; 81 b2=d[z1][z2][0]; 82 dij(z1,z2); 83 c1=d[x1][x2][0]; 84 c2=d[y1][y2][0]; 85 if(b1+c1
            
             =inf)101 printf("NO");102 else103 printf("%c\n%d",ch,ans);104 return 0;105 }
            
           
        
       
      
     

分层图跑DJ