哪位大佬帮我看看什么地方错了,数据只过了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();
}
全部评论

相关推荐

06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务