1 #include<iostream>  2 #include<cstdio>  3 #include<algorithm>  4 #include<vector>  5 #include<cstdlib>  6 #include<cmath>  7 #include<cstring>  8 using namespace std;  9 #define maxn 110 10 #define SIZE 1000000 11 #define llg long long  12 #define inf (llg)1e16 13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 14  15 llg n,m,k,A,B,C,dis[maxn*maxn][15],bj[maxn*maxn][maxn],se[maxn*maxn],head,tail; 16 llg p[5][4]; 17 vector<llg>a[maxn*maxn],val[maxn*maxn]; 18  19 llg num(llg x,llg y){return (x-1)*n+y;} 20  21 void link(llg x,llg y,llg z){a[x].push_back(y),val[x].push_back(z);} 22  23 struct node 24 { 25     llg x,y; 26 }dl[SIZE+5]; 27  28 void init() 29 { 30     p[1][0]=1,p[2][1]=1,p[3][0]=-1,p[4][1]=-1; 31     cin>>n>>k>>A>>B>>C; 32     for (llg i=1;i<=n*n;i++) scanf("%lld",&se[i]); 33     for (llg i=1;i<=n;i++) 34         for (llg j=1;j<=n;j++) 35             for (llg w=1;w<=4;w++) 36             { 37                 llg x=i+p[w][0],y=j+p[w][1]; 38                 if (x>n || x<1 || y>n || y<1) continue; 39                 if (w<=2) link(num(i,j),num(x,y),0); 40                 else link(num(i,j),num(x,y),B); 41             } 42     for (llg i=1;i<=n*n;i++) for (llg j=0;j<=k;j++) dis[i][j]=inf; 43     tail=1,head=0; 44     dl[1].x=1;dl[1].y=k; dis[1][k]=0; 45 } 46  47 void spfa() 48 { 49     llg x,v,y,w; 50     do 51     { 52         head%=SIZE; head++; 53         x=dl[head].x,y=dl[head].y; 54         w=a[x].size(); bj[x][y]=0; 55         if  (se[x] && y!=k) 56         { 57             if (dis[x][y]+A<dis[x][k]) 58             { 59                 dis[x][k]=dis[x][y]+A; 60                 if (!bj[x][k]) 61                 { 62                     bj[x][k]=1; 63                     tail%=SIZE; tail++; 64                     dl[tail].x=x,dl[tail].y=k; 65                 } 66             } 67             continue; 68         } 69         if (y!=0) 70         { 71             for (llg i=0;i<w;i++) 72             { 73                 v=a[x][i]; 74                 if (dis[v][y-1]>dis[x][y]+val[x][i]) 75                 { 76                     dis[v][y-1]=dis[x][y]+val[x][i]; 77                     if (!bj[v][y-1]) 78                     { 79                         bj[v][y-1]=1; 80                         tail%=SIZE; tail++; 81                         dl[tail].x=v;dl[tail].y=y-1; 82                     } 83                 } 84             } 85         } 86         if (y!=k && se[x]==0) 87         { 88             if (dis[x][k]>dis[x][y]+C+A) 89             { 90                 dis[x][k]=dis[x][y]+C+A; 91                 if (!bj[x][k]) 92                 { 93                     bj[x][k]=1; 94                     tail%=SIZE; tail++; 95                     dl[tail].x=x,dl[tail].y=k; 96                 } 97             } 98         } 99     }while(head!=tail);100 }101 102 int main()103 {104     yyj("car");105     init();106 //    k--;107     spfa();108     llg ans=inf;109     for (llg i=0;i<=k;i++) ans=min(ans,dis[n*n][i]);110     cout<<ans;111     return 0;112 }