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

2018-04-28 13:04:25


这题实在是坑...... 强制用广搜AC

别问我为什么没开循环队列

广搜时要注意判重,我运用了分层思想。

#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); 
}