P4009 汽车加油行驶问题

Luogu4009

直接最短路即可 , 见代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f*x;
}

const int N=101;
const int M=11;

int dis[N][N][M];bool a[N][N],inq[N][N][M];
int n,K,A,B,C,ans=INF;

struct Node{
    int x,y,k;
};
queue <Node> q;

int d[4][2]={1,0,0,1,0,-1,-1,0};

inline void BFS(){
    memset(dis,0x3f,sizeof dis);
    memset(inq,0,sizeof inq);
    q.push((Node){1,1,K});inq[1][1][K]=1;dis[1][1][K]=0;
    while(!q.empty()){
        int x=q.front().x,y=q.front().y,k=q.front().k;inq[x][y][k]=0;q.pop();
        if(a[x][y]&&k!=K){
            if(dis[x][y][k]+A<dis[x][y][K]){
                dis[x][y][K]=dis[x][y][k]+A;
                if(!inq[x][y][K]) 
                    q.push((Node){x,y,K}),inq[x][y][K]=1;
            }
            continue;
        }
        if(dis[x][y][k]+A+C<dis[x][y][K]){
            dis[x][y][K]=dis[x][y][k]+A+C;
            if(!inq[x][y][K])
                inq[x][y][K]=1,q.push((Node){x,y,K});
        }
        if(k>0)
        for(int i=0;i<4;i++){
            int tx=x+d[i][0],ty=y+d[i][1];
            if(tx<1||tx>n||ty<1||ty>n) continue;
            int cost=B*(tx<x||ty<y);
            if(dis[x][y][k]+cost<dis[tx][ty][k-1]){
                dis[tx][ty][k-1]=dis[x][y][k]+cost;
                if(!inq[tx][ty][k-1])
                    inq[tx][ty][k-1]=1,q.push((Node){tx,ty,k-1});
            }
        }
    }
}

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++) 
            a[i][j]=read();
    }
    BFS();
    for(int i=0;i<=K;i++)
        ans=min(ans,dis[n][n][i]);
    printf("%d\n",ans);
}

P4009 汽车加油行驶问题

原文：https://www.cnblogs.com/lizehon/p/10645177.html