P4009 汽车加油行驶问题 题解

(Updated: )
oi
,

当然食用spfa啦。 但本蒟蒻不会分层。所以就二维spfa啦。 基本思路就是：一开始先把(1,1)点的状态扔进队列。 然后分类讨论 详细见代码 丑陋无比的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define ll long long
#define mod 100003
#define E 1000010
using namespace std;//丑陋的头文件终于结束
inline ll read(){
    ll res=0,f=1;char ch=getchar();
    while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}//丑陋的读优
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}//丑陋的输优
//queue<ll> q;
//set<ll> s;
//priority_queue<ll> q1;
//priority_queue<ll,vector<ll>,greater<ll> > q2;
//list<ll> l;
//stack<ll> s;
int n,k,a,b,c;
int has[110][110];//有木有油箱
int dis[110][110][15];//当前状态的最小花费
struct node{
    int x,y,z;//状态记录，分别为x坐标、y坐标、还有多少油
};
struct queue{
    node val[10000000];int s,t;
    void clean(){
        memset(val,0,sizeof(val));
        s=0;t=0;//清空（貌似没有用到过）
    }
    void push(node tmp){
        ++t;
        t%=10000000;
        val[t]=tmp;//加入队尾
    }
    inline node front(){
        return val[(s+1)%10000000];//循环队列，get队首
    }
    void pop(){
        s++;//弹出
        s%=10000000;//循环队列
    }
    bool empty(){//判断是否为空
        if(s>=t) return 1;
        else return 0;
    }
}q;//队列
node make(int x,int y,int z){
    node pp;pp.x=x;pp.y=y;pp.z=z;
    return pp;
}//方便快捷一些
const int dx[]={0,0,1,-1},
          dy[]={1,-1,0,0};//四个方向
void print(){
    system("cls");
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int ss=2e9;
            for(int l=0;l<=k;l++) ss=min(ss,dis[i][j][l]);
            cout<<ss<<" ";
        }
        cout<<endl;
    }
}//调试输出函数
void spfa(){//spfa开始
    while(!q.empty()){
        node u=q.front();q.pop();
        int x=u.x,y=u.y,K=u.z;//取出队首元素
        if(K==0){//没油了
            if(has[x][y]==1){//真棒！这里就有油箱
                if(dis[x][y][K]+a<dis[x][y][k]){
                    dis[x][y][k]=min(dis[x][y][k],dis[x][y][K]+a);//加油花费a
                    q.push(make(x,y,k));
                }
            }else{//这里没有油箱
                if(dis[x][y][k]>dis[x][y][K]+c+a){
                    dis[x][y][k]=min(dis[x][y][k],dis[x][y][K]+c+a);//新建油箱花费c，加油花费a
                    q.push(make(x,y,k));
                }
            }
        }else{
            if(has[x][y]==1){//坑，如果经过油箱必须加油
                if(dis[x][y][K]+a<dis[x][y][k]){
                    dis[x][y][k]=dis[x][y][K]+a;//愉快的花费a
                    q.push(make(x,y,k));continue ;//因为加油，本次状态取消，直接退出
                }
            }
            for(int i=0;i<4;i++){
                int xx=x+dx[i],yy=y+dy[i];//四个方向
                if(xx>=1&&xx<=n&&yy>=1&&yy<=n){//判断是否越界
                    if(dis[xx][yy][K-1]>dis[x][y][K]+((i==1i==3)?b:0)){//如果往负方向花费b
                        dis[xx][yy][K-1]=dis[x][y][K]+((i==1i==3)?b:0);//更新
                        q.push(make(xx,yy,K-1));//保存状态
                    }
                }
            }

        }
//        print();
    }
}
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++){
            has[i][j]=read();
        }
    }//丑陋无比的读入
    memset(dis,63,sizeof(dis));//初始化
    dis[1][1][k]=0;//初始化
    q.push(make(1,1,k));//塞入队列
    spfa();//spfa
    int ans=2e9;//取最小值前设定最大
    for(int i=0;i<=k;i++) ans=min(ans,dis[n][n][i]);//更新，因为终点有很多状态，取最小值
    cout<<ans<<endl;//输出
    return 0;
}