929 - Number Maze

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

Why TLE???

Post by LazyTym » Wed Feb 04, 2015 11:29 am

i use priority queue and BFS. but i can not understand why getting TLE everytime????please anyone check my code ..........
My code below:

Code: Select all


#include<iostream>
#include<cstring>
#define M 1000000
#define INF 999999

using namespace std;
int dx[4]={-1,+1,0,0};
int dy[4]={0,0,-1,+1};
int A[999][999];
int row,col;


struct node {
    node* next;
    //node* pre;
    int index;
    int weight;
};
class PQueue {
    node* head;
public:
    PQueue(){
        head=NULL;
    }
    void add_with_priority(int key,int value) {

        node* newNode=new node;

        newNode->next=NULL;
        newNode->index=key;
        newNode->weight=value;

        if(head==NULL) {
            head=newNode;
        }
       if(head!=NULL) {

            node* prev=head;
            bool flag=false;
            node* cur=head;

            if(head->weight>newNode->weight) {
                head=newNode;
                prev=newNode;
                newNode->next=cur;
            }

            else {
                while(cur!=NULL) {
                //cout<<cur->weight<<endl;
                if(cur->index==newNode->index) {
                        cur->weight=newNode->weight;
                        flag=true;
                        break;
                    }
                if(cur->weight>newNode->weight) {

                    prev->next=newNode;
                    newNode->next=cur;
                    flag=true;
                    break;
                }
                prev=cur;
                cur=cur->next;
                }
                if(flag==false) {
                    prev->next=newNode;
            }
        }
    }
}

    int pop() {
        node* temp=new node;
        temp=head;
        int key=temp->index;
        head=head->next;
        delete temp;
        return key;
    }
    int IsEmpty(){
        if(head==NULL) return 1;
        return 0;
    }
    void print() {
        node* cur=head;
        while(cur!=NULL) {
            cout<<cur->index<<" ";
            cout<<cur->weight<<endl;
            cur=cur->next;
        }
    }

};


int BFS() {

    int visited[M];
    int dis[M];
    PQueue q;
    for(int i=0;i<row*col;i++)
    {
        dis[i]=INF;
        q.add_with_priority(i,INF);
        visited[i]=0;
    }

    dis[0]=0;

    q.add_with_priority(0,0);

    int x,y,w,c,p;

    while(!q.IsEmpty()) {

        p=q.pop();
        if(p==((row*col)-1)) break;
        if(visited[p]==0) {
            x=p/col;
            y=p%col;
            for(int i=0;i<4;i++) {
               int tx=x+dx[i];
               int ty=y+dy[i];
               if(tx>=0 && tx<row && ty>=0 && ty<col) {
                    w=A[tx][ty];
                    c=(tx*col)+ty;

                    if(dis[c]>dis[p]+w) {
                        dis[c]=dis[p]+w;
                        //cout<<"dis["<<c<<"]="<<dis[c]<<endl;
                        q.add_with_priority(c,dis[c]);
                    }
                    //q.add_with_priority(c,dis[c]);
               }
            }
        visited[p]=1;
        }
    }
    return dis[(row*col)-1];
}

int main()
{
    int test,node;
    cin>>test;
    while(test--) {
        cin>>row>>col;
        for(int i=0;i<row;i++) {
            for(int j=0;j<col;j++) {
                cin>>A[i][j];
            }
        }
        cout<<BFS()<<endl;;
    }
    return 0;
}


thanks in Advanced.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 929 - Number Maze

Post by brianfry713 » Wed Feb 04, 2015 8:21 pm

Don't triple post.
Read this thread.
Check input and AC output for thousands of problems on uDebug!

tonybeeth
New poster
Posts: 2
Joined: Mon Mar 14, 2016 10:11 pm

Re: 929 - Number Maze

Post by tonybeeth » Fri Jun 17, 2016 6:14 am

I need help with the idea of implementing a priority queue with 10 queues. I don't get the idea or how it's supposed to work. Thanks. :D

Post Reply

Return to “Volume 9 (900-999)”