P4009 汽车加油行驶问题

P4009 汽车加油行驶问题

最短路

清一色的spfa....送上一个堆优化Dijkstra吧（貌似代码还挺短）

顺便说一句，堆优化Dj跑分层图灰常好写

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

template <typename T> inline T min(T &a,T &b) {return a<b ?a:b;}

struct data{ //对于不同题目的要求，我们只需要在结构体中按题意增减变量即可

    int d,x,y,k; //d:费用 x,y:坐标 k:油量

    bool operator < (const data &tmp) const {return d>tmp.d;}

}; priority_queue <data> h;

int d1[]={,,,-};

int d2[]={,,-,};

int n,tk,a,b,c,ans=2e9,d[][][],oil[][];

int main(){

    scanf("%d%d%d%d%d",&n,&tk,&a,&b,&c);

    for(int i=;i<=n;++i)

        for(int j=;j<=n;++j)

            scanf("%d",&oil[i][j]);

    memset(d,,sizeof(d));

    h.push((data){d[tk][][]=,,,tk}); //优先队列直接放结构体

    while(!h.empty()){

        data u=h.top(); h.pop();

        if(u.d!=d[u.k][u.x][u.y]) continue; //记忆化

        if(!u.k) u.k=tk,u.d+=a+c; //没油了就新建一个油库并加油

        for(int i=;i<;++i){

            int r1=u.x+d1[i],r2=u.y+d2[i],cost= i> ? b:; //cost:当向左或向上是要加的费用

            if(r1<||r1>n||r2<||r2>n) continue;

            if(oil[r1][r2]){ //有油库必须加满

                if(u.d+cost+a<d[tk][r1][r2]){

                    d[tk][r1][r2]=u.d+cost+a;

                    h.push((data){d[tk][r1][r2],r1,r2,tk});

                }

            }else if(u.d+cost<d[u.k-][r1][r2]){ //普通的行驶

                d[u.k-][r1][r2]=u.d+cost;

                h.push((data){d[u.k-][r1][r2],r1,r2,u.k-});

            }

        }

    }

    for(int i=;i<=tk;++i) ans=min(ans,d[i][n][n]); //查找最小值

    printf("%d",ans);

    return ;

}