题目描述：

在这里插入图片描述

题解：

看了很多题解，无论什么解法都绕不开分层图
在本题中加满油的车每次可以移动K步，那么我们就可以建立一个K+1层的分层图，表示汽车油量k的状态（油量0...k），然后根据题目要求建图
首先我们规定(k从1开始)第k层第i行第j列点编号为(k-1) * n * n + (i-1) * n + j
首先我们从第k层(i,j)建立一条边到第k+1层(i,j),边权为0，相当于车原地不动（其实这一步可有可无）
然后肯定是否到达油站来详细分析：
当到达油站时，油会加满，所以无论当前为哪一层都要指向第一层指向一个边，边权为a（即加油费）。然后从第一层的(i,j)向第二层的四个方向指向边，因为当i和j减少时要化为b，所以指向(i-1,j)和(i,j-1)时边权为b，另外两个（i+1，j）和（i，j+1）边权为0，当然要注意当前点是否在图的边缘，以防止越界
当没到油站时，我们要向下一层的四个方向指向边，然后我们要模拟建立油站的情况，该点所有层均要向第一层生成一个有向边，边权为建立油站的费用+加油的费用（即a+c）
然后跑最大流或者spfa都可以

代码：

结合代码分析分析

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int INF=2e9;

int n,k,p,b,c,cnt;
int head[350005],dis[350005],q[900005];
bool vis[350005],oil;
struct node{
    int next,v,dis;
}a[900005];

void add(int x1,int y1,int z1,int x2,int y2,int z2,int dis){
    int u=n*n*(z1-1)+(x1-1)*n+y1;
    int v=n*n*(z2-1)+(x2-1)*n+y2;
    a[++cnt]=(node){head[u],v,dis};
    head[u]=cnt;
}

void spfa(){
    for(int i=1;i<=n*n*(k+1);++i) dis[i]=INF;
    queue<int>q; 
    //int hd=1,tl=1;
    int s=1;
    q.push(1);
    vis[s]=1;
    dis[1]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=a[i].next){
            if(dis[a[i].v]>dis[u]+a[i].dis){
                dis[a[i].v]=dis[u]+a[i].dis;
                if(!vis[a[i].v]){
                    vis[a[i].v]=1;
                    q.push(a[i].v);
                }
            }
        }
    }
}

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,dis[n*n*i]);
    printf("%d\n",ans);
    return 0;
}