[洛谷 4009]汽车加油行驶问题

题目链接

https://www.luogu.org/problem/P4009

题解

（据说可以用费用流做，但分层图最短路的做法更好理解）

设 \(f(x,y,v)\) 表示在 \((x,y)\)，剩余油量为 \(v\) 的最小开销。

根据题意枚举四个方向转移即可。（显然只有在没油的时候才会考虑增设加油站）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct node
{
 int x,y,val;
};
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
int ma[105][105],dist[105][105][15],vis[105][105][15];
queue<node> q;
int main()
{
 int n,k,a,b,c;
 scanf("%d%d%d%d%d",&n,&k,&a,&b,&c);
 for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
   scanf("%d",&ma[i][j]);
 memset(dist,INF,sizeof(dist));
 dist[1][1][k]=0,vis[1][1][k]=1;
 q.push({1,1,k});
 while(!q.empty())
 {
  int x=q.front().x,y=q.front().y,val=q.front().val;
  q.pop();
  vis[x][y][val]=0;
  for(int i=0;i<4;i++)
  {
   int nx=x+dx[i],ny=y+dy[i],p=0,nv=val-1;
   if(nx<=0||nx>n||ny<=0||ny>n)continue;
   if(nx<x||ny<y)p+=b;
   if(ma[nx][ny])p+=a,nv=k;
   if(nv<=0&&(!ma[nx][ny]))
    if(nx!=n||ny!=n)
     p+=a+c,nv=k;
   if(dist[nx][ny][nv]>dist[x][y][val]+p)
   {
    dist[nx][ny][nv]=dist[x][y][val]+p;
    if(!vis[nx][ny][nv])
    {
     vis[nx][ny][nv]=1;
     q.push({nx,ny,nv});
    }
   }
  }
 }
 int ans=INF;
 for(int i=0;i<k;i++)
  ans=min(ans,dist[n][n][i]);
 printf("%d\n",ans);
 return 0;
}