题意

思路

假的网络流

由于无法直接储存油量这个状态，加上k很小，可以把原图分层，分为k+1层图，分别表示当前油量为0~k

连边

1. 对于满油的第k层，连给四个方向，如果向回走了权值为B，否则为0，表示走一步

2. 对于非满油层，如果当前点是加油站，那么它只有一条指向第k层对应点的边，权值为A，表示加一次油

3. 对于非满油层，如果当前节点不是加油站，那么它可以连给下一层对应的四个方向，同1；它也有一条连向第k层对应点的边，权值为A+C，表示建立加油站并且加一次油（由于网格图上的每一个点最多走一次，所以这样连边的正确性可以保证）

4. 最后将终点所对应的k+1个点连给汇点t，边权为0

从第k层的s点出发跑最短路，dis[t]，即为答案

Code：

#include
    
     #define N 200005#define M 2000005using namespace std;int n,k,A,B,C,s,t;int a[105][105];int dis[N];bool vis[N];struct Node{    int u,dis;    bool operator < (const Node a)const    {        return a.dis
     
       q;    q.push((Node){s,0});    dis[s]=0;    while(!q.empty())    {        int u=q.top().u;q.pop();        if(vis[u]) continue;        vis[u]=1;        for(int i=head[u];i;i=edge[i].next)        {            int v=edge[i].to;            if(dis[v]>dis[u]+edge[i].dis)            {                dis[v]=dis[u]+edge[i].dis;                if(!vis[v]) q.push((Node){v,dis[v]});            }        }    }}int main(){    scanf("%d%d%d%d%d",&n,&k,&A,&B,&C);    s=1;t=N-5;    for(int i=1;i<=n;++i)        for(int j=1;j<=n;++j)            scanf("%d",&a[i][j]);        //代码中i=0为满油层    for(int i=0;i<=k;++i)        for(int j=1;j<=n;++j)            for(int p=1;p<=n;++p)            {                int id=(j-1)*n+p,step=n*n;                if(!a[j][p]||!i)//不是加油站，可以向四周连边；或者满油位置                 {                    if(i!=k)//还有油                     {                        if(p!=n) add_edge(step*i+id,step*(i+1)+id+1,0);//向右                        if(p!=1) add_edge(step*i+id,step*(i+1)+id-1,B);//向左                        if(j!=n) add_edge(step*i+id,step*(i+1)+id+n,0);//向下                        if(j!=1) add_edge(step*i+id,step*(i+1)+id-n,B);//向上                    }                }                if(a[j][p]&&i) add_edge(step*i+id,id,A);//加油站                if(!a[j][p]&&i) add_edge(step*i+id,id,A+C);//新建加油站             }    for(int i=0;i<=k;++i) add_edge(n*n*(i+1),t,0);//连终点     dijkstra(s);    cout<
      
       <