56分救助

P2895 [USACO08FEB] Meteor Shower S

gaoyangyang @ 2024-07-20 10:35:27

#include<bits/stdc++.h> 
using namespace std; 
short int n; 
short int t[50001],x[50001],y[50001]; 
short int dx[4]={1,0,-1,0}; 
short int dy[4]={0,1,0,-1}; 
short int a[400][400]; 
struct node 
{ 
    short int x,y,t; short int pre;
}que[17000000];
int main() 
{
    cin>>n;
    memset(a,-1,305*305);
    for (int i=0; i<n; i++) 
    {
        cin>>x[i]>>y[i]>>t[i];

        if(a[x[i]][y[i]]==-1||a[x[i]][y[i]]>t[i])
            a[x[i]][y[i]]=t[i];
        if(x[i]-1>=0&&(a[x[i]-1][y[i]]==-1||a[x[i]-1][y[i]]>t[i]))
            a[x[i]-1][y[i]]=t[i];
        if(y[i]-1>=0&&(a[x[i]][y[i]-1]==-1||a[x[i]][y[i]-1]>t[i]))
            a[x[i]][y[i]-1]=t[i];
        if(a[x[i]+1][y[i]]==-1||a[x[i]+1][y[i]]>t[i])
            a[x[i]+1][y[i]]=t[i];
        if(a[x[i]][y[i]+1]==-1||a[x[i]][y[i]+1]>t[i])
            a[x[i]][y[i]+1]=t[i];
    }
    if (a[0][0]==-1) 
    {
        cout<<0;
        return 0;
    }
    int head,tail; 
    head=0;tail=1; 
    que[tail].x=0; 
    que[tail].y=0; 
    que[tail].t=0; 
    que[tail].pre=0; 
    while (head<tail) 
    { 
        head++; 
        for (int i=0;i<4;i++) 
        { 
            int xx=que[head].x+dx[i]; 
            int yy=que[head].y+dy[i]; 
            if (xx>=0 and yy>=0 and (que[head].t+1<a[xx][yy] or a[xx][yy]==-1))
            { 
                tail++; 
                que[tail].x=xx; 
                que[tail].y=yy; 
                que[tail].t=que[head].t+1; 
                que[tail].pre=head; 
                if (a[que[tail].x][que[tail].y]==-1) 
                {
                    cout<<que[tail].t; return 0; 
                } 
            } 
        } 
    } 
    cout<<-1; 
    return 0; 
}

MLE 了....报错


by gaoyangyang @ 2024-07-20 10:35:51

还有RE


|