P5195 [USACO05DEC]Knights of Ni S

xingke233 / 2024-11-09 / 原文

为什么没有题解用优先队列，来个优先队列的。

先从起点 BFS 一遍，把到所有能到达灌木丛放入优先队列。

因为防止有些离终点近但不是最优的灌木丛更新答案。

再跑一遍优先队列 BFS 。

#include<bits/stdc++.h>
using namespace std;
#define LL long long

LL n, m, a[1002][1002], x1, y, sx, sy, f_x[4] = {1, -1, 0, 0}, f_y[4] = {0, 0, 1, -1}, t;
LL d[1000005][3],d1,d2,f1,f2;
bool b[1002][1002],u[1002][1002];
struct Node
{
    int x,y,z;
    Node(int x,int y,int z):x(x),y(y),z(z){}
    bool operator <(Node a) const  {  return z < a.z; }
    bool operator >(Node a) const  {  return z > a.z; }
};
    priority_queue<Node, vector<Node>, greater<Node> > f;  
    //stl大法好
inline LL read(){
    LL s=0,w=1;char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-'){w=-1;}ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return s*w;
}

void print(LL x){
    char F[200];LL cnt=0;
    if(x<0) {x=-x;putchar('-');}
    if(x==0){putchar('0');putchar('\n');return ;}
    while(x){F[++cnt]=x%10;x/=10;}
    while(cnt){putchar(F[cnt--]+'0');}
    putchar('\n');
    return ;
}

int main(){
    /*freopen("2.in", "r", stdin);
    freopen("2.out", "w", stdout);*/
    m = read(), n = read();
    for (int i = 1; i <= n;i++){
        for (int j = 1; j <= m;j++){
            a[i][j] = read();
            if(a[i][j]==2)
                x1 = i, y = j;
        }
    }
    d[d1][0]=(x1);
    d[d1][1]=(y);
    d[d1][2]=(0);
    b[x1][y] = 1;
    while(d1<=d2){//裸的bfs
        x1 = d[d1][0];
        y = d[d1][1];
        t = d[d1][2];
        for (int i = 0; i < 4;i++){
            int xx = x1 + f_x[i], yy = y + f_y[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!b[xx][yy]&&a[xx][yy]!=3&&a[xx][yy]!=1){
                d[++d2][0]=(xx);
                d[d2][1]=(yy);
                d[d2][2]=(t+1);
                b[xx][yy] = 1;
                if(a[xx][yy]==4){
                //cout<<xx<<" "<<yy<<" "<<t+1<<endl;
                f.push(Node(xx, yy, t + 1));//放到优先队列里
                }
            }
        }
        d1++;
    }
    while(!f.empty()){//第二次优先队列bfs
        x1 = f.top().x;
        y = f.top().y;
        t = f.top().z;
        if(a[x1][y]==3){//终点第一次取出时就是最优答案
            print(t);
            return 0;
        }
        for (int i = 0; i < 4;i++){
            int xx = x1 + f_x[i], yy = y + f_y[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!u[xx][yy]&&a[xx][yy]!=1){
                f.push(Node(xx,yy,t+1));
                u[xx][yy] = 1;
            }
        }
        f.pop();
    }
    return 0;
}

成功跑到 $85ms$。