洛谷4009 汽车加油行驶问题

题意

给一个 $N\times N$ 网格图，汽车从 $(1,1)$ 走到 $(N,N)$ 。

网格图中有加油站，汽车到了加油站就会被强制加油花费 $A$ ；如果没油了也可以设立一个油库并加油，花费 $C+A$ ；如果往回走（ $X,Y$ 坐标有一个减小）会花费 $B$ 。

汽车邮箱容量为 $K$ ，每走一条边消耗 $1$ 单位的油。

求花费的最小值。

题解

朴素的 $bfs$ 就可以过，不过会成为反向最优解的第 $3$ 页。

搜索过程中用queue维护一个四元组 $(x,y,lef,now)$ ，并用 $ans[x][y][left]$ 记录最优解。上述变量代表当前在 $(x,y)$ ，剩余油量 $lef$ ，花费 $now$ 。

然后对加油分类讨论就行了。

#include<bits/stdc++.h>
#define T tuple<int,int,int,int>
#define TIE tie(x,y,lef,now)
#define mt make_tuple

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

bool have_o[105][105];
int fx[4]={0,0,1,-1},fy[4]={1,-1,0,0};
int n,k,a,b,c,ans[105][105][15],x,y,lef,now;

inline int bfs()
{
    memset(ans,0x3f,sizeof(ans));
    queue <T> q;
    q.push(mt(1,1,k,0));
    while (!q.empty())
    {
        TIE=q.front(); q.pop();
        if (now>=ans[x][y][lef]) continue;
        ans[x][y][lef]=now;
        if (have_o[x][y]) lef=k,now+=a;
        for (int i=0;i<4;i++)
        {
            int tx=x+fx[i],ty=y+fy[i],nxt=now,nxt_lef=lef;
            if (tx<1 || tx>n || ty<1 || ty>n) continue;
            nxt+=(i==0 || i==2) ? 0 : b;
            if (!lef) nxt_lef=k,nxt+=a+c;
            nxt_lef--;
            q.push(mt(tx,ty,nxt_lef,nxt));
        }
    }
    int mn=1e9;
    for (int i=0;i<=k;i++) mn=min(mn,ans[n][n][i]);
    return mn;
}

int main()
{
    n=read(); k=read(); a=read(); b=read(); c=read();
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) have_o[i][j]=read();
    printf("%d",bfs());
    return 0;
}