题解 P4009 【汽车加油行驶问题】
Adove
2018-03-21 20:50:23
本题适合作分层图最短路的模板题（~~当然你也可以用来练最小费用最大流~~。
分层图大概长这样↓（这是费用流建图，最短路去掉源汇点即可）
图分为k+1层，箭头所指可以直达，蓝线自下而上需要付费（即最短路边权，费用流费用），黄线自高层连到基层需要付费（同上），最后在每一层的右下扫一遍取最小值即可。
上代码↓
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=2e9;
int n,k,p,b,c,np;
int h[350005],ln[350005],q[900005];
bool vis[350005],oil;
struct rpg{
int li,nx,ln;
}a[900005];
void add(int x1,int y1,int z1,int x2,int y2,int z2,int ln){
int ls=n*n*(z1-1)+(x1-1)*n+y1,nx=n*n*(z2-1)+(x2-1)*n+y2;
a[++np]=(rpg){h[ls],nx,ln};
h[ls]=np;
}
void spfa(){
for(int i=1;i<=n*n*(k+1);++i) ln[i]=INF;
int hd=1,tl=1;
q[hd]=1;
ln[1]=0;
while(hd<=tl){
int nw=q[hd++];
vis[nw]=0;
for(int i=h[nw];i;i=a[i].li){
if(ln[a[i].nx]>ln[nw]+a[i].ln){
ln[a[i].nx]=ln[nw]+a[i].ln;
if(!vis[a[i].nx]){
vis[a[i].nx]=1;
q[++tl]=a[i].nx;
}
}
}
}
}
int main(){
scanf("%d%d%d%d%d",&n,&k,&p,&b,&c);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
scanf("%d",&oil);
for(int l=1;l<=k;++l){
add(i,j,l,i,j,l+1,0);
}
if(oil){
for(int l=2;l<=k+1;++l){
add(i,j,l,i,j,1,p);
}
if(i<n) add(i,j,1,i+1,j,2,0);
if(j<n) add(i,j,1,i,j+1,2,0);
if(i>1) add(i,j,1,i-1,j,2,b);
if(j>1) add(i,j,1,i,j-1,2,b);
}else{
for(int l=1;l<=k;++l){
if(i<n) add(i,j,l,i+1,j,l+1,0);
if(j<n) add(i,j,l,i,j+1,l+1,0);
if(i>1) add(i,j,l,i-1,j,l+1,b);
if(j>1) add(i,j,l,i,j-1,l+1,b);
}for(int l=2;l<=k+1;++l){
add(i,j,l,i,j,1,p+c);
}
}
}
}spfa();
int ans=INF;
for(int i=1;i<=k+1;++i) ans=min(ans,ln[n*n*i]);
printf("%d\n",ans);
return 0;
}
```