题解 P4009 【汽车加油行驶问题】

这题实在是坑...... 强制用广搜AC 别问我为什么没开循环队列 广搜时要注意判重，我运用了分层思想。 ```cpp #include <bits/stdc++.h> using namespace std; struct Node{int x,y,money,power;} q[1000001]; int st,en,a,b,c,arr[101][101][21],l,mx,mz[101][101], dx[] = {1,0,-1,0},dy[] = {0,1,0,-1}; int ans = INT_MAX; int main () { scanf("%d%d%d%d%d",&l,&mx,&a,&b,&c); for (int i = 1;i <= l;++i) for (int j = 1;j <= l;++j) scanf("%d",&mz[i][j]); arr[1][1][mx] = 0; q[en++] = {1,1,0,mx}; for (int i = 1;i <= l;++i) for (int j = 1;j <= l;++j) for (int k = 0;k <= 10;++k) arr[i][j][k] = INT_MAX;//arr里记录的是在坐标分别为i,j的情况下邮箱里还剩下k油时花掉的最小金钱 while (st != en) //BFS正片 { Node nd = q[st++]; for (int i = 0;i < 4;++i) { int nx = nd.x + dx[i],ny = nd.y + dy[i],nm = nd.money; if(nx <= 0 || nx > l || ny <= 0 || ny > l) continue; if(nx < nd.x || ny < nd.y) nm += b;//如果是逆行 if(mz[nx][ny]) //此处有加油站 { nm += a; if(arr[nx][ny][mx] <= nm) continue; //以花钱更少的路径到此 arr[nx][ny][mx] = nm; q[en++] = {nx,ny,nm,mx};//入队 } else { if(nd.power == 1) //没油啦 { if(nx == l && ny == l) { if(nm < ans) ans = nm; continue; } if(arr[nx][ny][mx] <= nm + c + a) continue; arr[nx][ny][mx] = nm + c + a;//原地制造加油站（不用标记，没有一辆车会闲的无聊开来开去） q[en++] = {nx,ny,nm + c + a,mx}; } else {//还能撑 if(nx == l && ny == l) { if(nm < ans) ans = nm; continue; } bool ok = 1; for (int i = nd.power - 1;i <= mx;++i) //花钱是否最少 if(arr[nx][ny][i] <= nm) { ok = 0;break; } if(!ok) continue; arr[nx][ny][nd.power - 1] = nm; q[en++] = {nx,ny,nm,nd.power - 1}; } } } } printf("%d",ans); } ```