哪位大佬帮我看看什么地方错了,数据只过了50%

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
const int MAXN=510;

typedef pair<int,int> PII;
typedef pair<int,PII> PIII;

//map<PII,int> mpp;
bool st[MAXN][MAXN];

int q,n,m;
long long mp[MAXN][MAXN];
int vis [MAXN][MAXN];
long long  dist[MAXN][MAXN];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
long long mint=0x3f3f3f3f;

int disjkstra()
{
    
   
    priority_queue<PIII,vector<PIII>, greater<PIII> > heap ;// 每次弹出最小的点,所以用小根堆
    
    dist[1][1]=1e18,dist[n][m]=1e18;
    for(int i=2;i<=n;i++) 
    {
        if(mp[i][1]!=1e18) 
        {
            PIII kk;
            kk.first=mp[i][1],kk.second.first=i,kk.second.second=1;
            heap.push(kk);
            dist[i][1]=mp[i][1];
           
        }
    }
    
     for(int i=1;i<m;i++) 
    {
        if(mp[n][i]!=1e18) 
        {
            PIII kk;
            kk.first=mp[n][i],kk.second.first=n,kk.second.second=i;
            heap.push(kk);
            dist[n][i]=mp[n][i];

        }
    }
    // 将左边和下边的符合条件的点放进堆里
    
    while(!heap.empty())
    {
        PIII top=heap.top();
        heap.pop();
        long long  distance = top.first; 
        PII var=top.second; int varx=var.first,vary=var.second;
        
        if(varx==1||vary==m)  //当碰到上面的和右边的点时,说明这个围墙已经搭建好,判断这时distance是否是最小
        {
            mint=min(mint,distance);
            continue;//由于围墙已经搭建好了,所以对周围的点做松弛操作没有必要
        }
        
        if(st[varx][vary]) continue; //如果该点的最短距离已经被确认了,则无需再做松弛操作 
        else st[varx][vary]=true;
        
        for(int i=0;i<4;i++)  // 给四周的点做松弛操作
        {
            int xx=varx+dx[i],yy=vary+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!st[xx][yy]) // 相比于前面的大佬稍微优化了一下,因为如果改点已经确定,则该点无需再入堆
            {
                if(distance+mp[xx][yy]<dist[xx][yy])//只有当改点减小了才会对周围的点做松弛操作,所以不符合条件的点不必要放入
                {
                    dist[xx][yy] =distance+mp[xx][yy];
                    PIII kk;
                    kk.first=dist[xx][yy],kk.second.first=xx,kk.second.second=yy;
                    heap.push(kk);// 将符合条件的点放入堆中
                    
                }
            }
        }
     
        
    }
    if(mint==1e18) return -1;
    else return mint;
    
}
void sc()
{
    //memset(st,0,sizeof st);
    mint=1e18;
    
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=m;j++) 
        {
            cin>>mp[i][j];
            if(mp[i][j]==-1) mp[i][j]=0;
            else if(mp[i][j]==0) mp[i][j]=1e18;   
            st[i][j]=false;
            dist[i][j]=1e18;
        }
    cout<<disjkstra()<<endl;
    
}
int main()
{
    cin>>q>>n>>m;
    while(q--) sc();
}
全部评论

相关推荐

评论
点赞
收藏
分享
牛客网
牛客企业服务