说好的网络流24题呢……上次是状压dp，这次怎么又最短路了……
不过倒是用这题好好学了一下分层图最短路
把每一个位置$(x,y)$，油量剩余$k$表示为一个状态，然后转化成一个$n$进制数，这样每一个状态都可以唯一表示。能互相转移的状态之间连有向边，然后跑一个最短路就行了
具体细节看代码好了……细节太多说不清楚……
ps：据说还可以用这个思想跑费用流，我估摸着大概是建源$S$和汇$T$，$S$向起点连，终点向$T$连，容量$inf$，费用$0$，然后各个状态之间的容量都是$1$，费用就是对应的转移的代价，跑个最小费用流就好了，因为用的也是spfa，似乎没啥区别（这整个ps都是这傻逼在口胡切勿当真）
//minamoto
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,:;}
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
const int N=,M=,inf=0x3f3f3f3f;
int n,k,p,b,c,tot;
bool vis[N],oil;
int d[N],q[M];
int head[N],Next[M],edge[M],ver[M];
inline void add(int x1,int y1,int z1,int x2,int y2,int z2,int e){
//可以理解成将这一个状态转化为一个n进制数
int u=n*n*(z1-)+(x1-)*n+y1,v=n*n*(z2-)+(x2-)*n+y2;
ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;
}
void spfa(){
for(int i=;i<=n*n*(k+);++i) d[i]=inf;
int h,t;q[h=t=]=,d[]=;
while(h<=t){
int u=q[h++];
vis[u]=;
for(int i=head[u];i;i=Next[i]){
int v=ver[i];
if(d[v]>d[u]+edge[i]){
d[v]=d[u]+edge[i];
if(!vis[v]){
vis[v]=,q[++t]=v;
}
}
}
}
}
int main(){
n=read(),k=read(),p=read(),b=read(),c=read();
//k能走几条路，p加油费用，b逆行费用，c增设费用
for(int i=;i<=n;++i){
for(int j=;j<=n;++j){
oil=read();
for(int l=;l<=k;++l) add(i,j,l,i,j,l+,);
if(oil){
//如果不满，强制加满
//然后要往边上走的话油就变为2了
for(int l=;l<=k+;++l) add(i,j,l,i,j,,p);
if(i<n) add(i,j,,i+,j,,);
if(j<n) add(i,j,,i,j+,,);
if(i>) add(i,j,,i-,j,,b);
if(j>) add(i,j,,i,j-,,b);
}
else{
for(int l=;l<=k;++l){
if(i<n) add(i,j,l,i+,j,l+,);
if(j<n) add(i,j,l,i,j+,l+,);
if(i>) add(i,j,l,i-,j,l+,b);
if(j>) add(i,j,l,i,j-,l+,b);
}
//增设加油站
for(int l=;l<=k+;++l) add(i,j,l,i,j,,p+c);
}
}
}
spfa();
int ans=inf;
//终点的每一个状态：y+(x-1)*n+(k-1)*n*n
//即n+(n-1)*n+(k-1)*n*n=n*n+(k-1)*n*n=k*n*n
for(int i=;i<=k+;++i) cmin(ans,d[n*n*i]);
printf("%d\n",ans);
return ;
}