说好的网络流24题呢……上次是状压dp，这次怎么又最短路了……
不过倒是用这题好好学了一下分层图最短路
把每一个位置$(x,y)$，油量剩余$k$表示为一个状态，然后转化成一个$n$进制数，这样每一个状态都可以唯一表示。能互相转移的状态之间连有向边，然后跑一个最短路就行了
具体细节看代码好了……细节太多说不清楚……
ps：据说还可以用这个思想跑费用流，我估摸着大概是建源$S$和汇$T$，$S$向起点连，终点向$T$连，容量$inf$，费用$0$，然后各个状态之间的容量都是$1$，费用就是对应的转移的代价，跑个最小费用流就好了，因为用的也是spfa，似乎没啥区别（这整个ps都是这傻逼在口胡切勿当真）
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} 9 inline int read(){ 10 #define num ch-'0' 11 char ch;bool flag=0;int res; 12 while(!isdigit(ch=getc())) 13 (ch=='-')&&(flag=true); 14 for(res=num;isdigit(ch=getc());res=res*10+num); 15 (flag)&&(res=-res); 16 #undef num 17 return res; 18 } 19 const int N=350005,M=900005,inf=0x3f3f3f3f; 20 int n,k,p,b,c,tot; 21 bool vis[N],oil; 22 int d[N],q[M]; 23 int head[N],Next[M],edge[M],ver[M]; 24 inline void add(int x1,int y1,int z1,int x2,int y2,int z2,int e){ 25 //可以理解成将这一个状态转化为一个n进制数 26 int u=n*n*(z1-1)+(x1-1)*n+y1,v=n*n*(z2-1)+(x2-1)*n+y2; 27 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e; 28 } 29 void spfa(){ 30 for(int i=1;i<=n*n*(k+1);++i) d[i]=inf; 31 int h,t;q[h=t=1]=1,d[1]=0; 32 while(h<=t){ 33 int u=q[h++]; 34 vis[u]=0; 35 for(int i=head[u];i;i=Next[i]){ 36 int v=ver[i]; 37 if(d[v]>d[u]+edge[i]){ 38 d[v]=d[u]+edge[i]; 39 if(!vis[v]){ 40 vis[v]=1,q[++t]=v; 41 } 42 } 43 } 44 } 45 } 46 int main(){ 47 n=read(),k=read(),p=read(),b=read(),c=read(); 48 //k能走几条路，p加油费用，b逆行费用，c增设费用 49 for(int i=1;i<=n;++i){ 50 for(int j=1;j<=n;++j){ 51 oil=read(); 52 for(int l=1;l<=k;++l) add(i,j,l,i,j,l+1,0); 53 if(oil){ 54 //如果不满，强制加满 55 //然后要往边上走的话油就变为2了 56 for(int l=2;l<=k+1;++l) add(i,j,l,i,j,1,p); 57 if(i<n) add(i,j,1,i+1,j,2,0); 58 if(j<n) add(i,j,1,i,j+1,2,0); 59 if(i>1) add(i,j,1,i-1,j,2,b); 60 if(j>1) add(i,j,1,i,j-1,2,b); 61 } 62 else{ 63 for(int l=1;l<=k;++l){ 64 if(i<n) add(i,j,l,i+1,j,l+1,0); 65 if(j<n) add(i,j,l,i,j+1,l+1,0); 66 if(i>1) add(i,j,l,i-1,j,l+1,b); 67 if(j>1) add(i,j,l,i,j-1,l+1,b); 68 } 69 //增设加油站 70 for(int l=2;l<=k+1;++l) add(i,j,l,i,j,1,p+c); 71 } 72 } 73 } 74 spfa(); 75 int ans=inf; 76 //终点的每一个状态：y+(x-1)*n+(k-1)*n*n 77 //即n+(n-1)*n+(k-1)*n*n=n*n+(k-1)*n*n=k*n*n 78 for(int i=1;i<=k+1;++i) cmin(ans,d[n*n*i]); 79 printf("%d ",ans); 80 return 0; 81 }