35分求调

ACdreamer @ 2024-08-25 22:54:01

#include<bits/stdc++.h>
using namespace std;
int m,ans,t,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},ma[310][310],d[310][310];
struct s{
    int x,y,t;
}meteor[50010];
queue<pair<int,int>>q;
bool vis[310][310];
void bfs()
{
    while(!q.empty())
    {
        auto u=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=u.first+dx[i];
            int y=u.second+dy[i];
            if(x>=0&&x<=300&&y>=0&&y<=300&&(d[u.first][u.second]<ma[x][y]-1||ma[x][y]==-1)&&!vis[x][y])
            {
                q.push({x,y});
                vis[x][y]=true;
                //cout<<x<<"  "<<y<<endl;
                d[x][y]=d[u.first][u.second]+1;
            }
        }
    }
}
int main()
{
    cin>>m;
    ans=0x3f3f3f3f;
    int xx,yy;
    memset(ma,0x3f3f3f3f,sizeof ma);
    for(int i=1;i<=m;i++)
    {
        cin>>meteor[i].x>>meteor[i].y>>meteor[i].t;
        xx=meteor[i].x;
        yy=meteor[i].y;
        ma[xx][yy]=meteor[i].t;
        xx++;
        if(xx>=0&&xx<=300&&yy>=0&&yy<=300)ma[xx][yy]=min(meteor[i].t,ma[xx][yy]);
        xx--;yy++;
        if(xx>=0&&xx<=300&&yy>=0&&yy<=300)ma[xx][yy]=min(meteor[i].t,ma[xx][yy]);
        xx--;yy--;
        if(xx>=0&&xx<=300&&yy>=0&&yy<=300)ma[xx][yy]=min(meteor[i].t,ma[xx][yy]);
        xx++;yy--;
        if(xx>=0&&xx<=300&&yy>=0&&yy<=300)ma[xx][yy]=min(meteor[i].t,ma[xx][yy]);
    }
    q.push({0,0});
    memset(d,-1,sizeof d);
    d[0][0]=0;
    vis[0][0]=true;
    bfs();
    for(int i=0;i<=300;i++)
    {
        for(int j=0;j<=300;j++)
        {
            if(ma[i][j]==0x3f3f3f3f)
            {
                ans=min(ans,d[i][j]);
            }
        }
    }
    if(ans==0x3f3f3f3f)cout<<-1;
    else cout<<ans;
}

by ACdreamer @ 2024-08-26 06:57:43

#include<bits/stdc++.h>
using namespace std;
int m,ans,t,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},ma[310][310],d[310][310];
struct s{
    int x,y,t;
}meteor[50010];
queue<pair<int,int>>q;
bool vis[310][310];
void bfs()
{
    while(!q.empty())
    {
        auto u=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=u.first+dx[i];
            int y=u.second+dy[i];
            if(x>=0&&x<=300&&y>=0&&y<=300&&(d[u.first][u.second]<ma[x][y]-1||ma[x][y]==-1)&&!vis[x][y])
            {
                q.push({x,y});
                vis[x][y]=true;
                //cout<<x<<"  "<<y<<endl;
                d[x][y]=d[u.first][u.second]+1;
            }
        }
    }
}
int main()
{
    cin>>m;
    ans=0x3f3f3f3f;
    int xx,yy;
    memset(ma,0x3f3f3f3f,sizeof ma);
    for(int i=1;i<=m;i++)
    {
        cin>>meteor[i].x>>meteor[i].y>>meteor[i].t;
        xx=meteor[i].x;
        yy=meteor[i].y;
        ma[xx][yy]=meteor[i].t;
        xx++;
        if(xx>=0&&xx<=300&&yy>=0&&yy<=300)ma[xx][yy]=min(meteor[i].t,ma[xx][yy]);
        xx--;yy++;
        if(xx>=0&&xx<=300&&yy>=0&&yy<=300)ma[xx][yy]=min(meteor[i].t,ma[xx][yy]);
        xx--;yy--;
        if(xx>=0&&xx<=300&&yy>=0&&yy<=300)ma[xx][yy]=min(meteor[i].t,ma[xx][yy]);
        xx++;yy--;
        if(xx>=0&&xx<=300&&yy>=0&&yy<=300)ma[xx][yy]=min(meteor[i].t,ma[xx][yy]);
    }
    q.push({0,0});
    memset(d,-1,sizeof d);
    d[0][0]=0;
    vis[0][0]=true;
    bfs();
    for(int i=0;i<=300;i++)
    {
        for(int j=0;j<=300;j++)
        {
            if(ma[i][j]==0x3f3f3f3f&&d[i][j]!=-1)
            {
                ans=min(ans,d[i][j]);
                //cout<<d[i][j]<<" ";
            }
        }
        //cout<<endl;
    }
    if(ans==0x3f3f3f3f)cout<<-1;
    else cout<<ans;
}

改了一下，现在71分