Bellman Ford queue based implementation c++

#include<bits/stdc++.h>
using namespace std;


#define NULL_VALUE -999999
#define SUCCESS_VALUE 999999
///DONE SUCCESFULLY

class ListNode//determines that it is a pure singly linked list
{
public:
    int item;
    ListNode * next;
};


class LinkedListWithTail
{

    ListNode * list;
    ListNode * tail;
    int length;

public:
    LinkedListWithTail()
    {
        list = NULL;  //initially set to NULL
        tail = NULL;
        length = 0;
    }

    int getLength()
    {
        return length;
    }

    ///add required codes to set up tail pointer
    int insertItem(int item)  //insert at the beginning
    {///task: 6
        ListNode * newNode ;
        newNode = new ListNode() ;
        newNode->item = item ;
        if(list == 0){//initially empty list
            newNode->next = list;
            list = tail = newNode;
        }
        else{//non empty list
            newNode->next = list;
            list = newNode;
            ///no need to change the tail
        }
        length++;
        return SUCCESS_VALUE;
    }

    //add required codes to set up tail pointer
    int deleteItem(int item)///task  - 06(connect the tail pointer properly)
    {
        ListNode *temp, *prev ;
        temp = list ; //start at the beginning
        while (temp != 0)
        {
            if (temp->item == item) break ;
            prev = temp;
            temp = temp->next ; //move to next node
        }
        if (temp == 0) return NULL_VALUE ; //item not found to delete
        if (temp == list) //delete the first node
        {
            list = list->next ;
            delete temp ;
            length--;
        }
        else//found in middle or last position
        {
            prev->next = temp->next ;
            delete temp;
            length--;
        }
        ///here list maybe occurs as NULL
        tail = list;
        while(tail != NULL && tail->next != 0){//tail will consist of at least one node
            tail = tail->next;
        }
        return SUCCESS_VALUE ;
    }

    //add required codes to set up tail pointer
    ListNode * searchItem(int item)
    {
        ListNode * temp ;
        temp = list ; //start at the beginning
        while (temp != 0)
        {
            if (temp->item == item) return temp ;
            temp = temp->next ; //move to next node
        }
        return 0 ; //0 means invalid pointer in C, also called NULL value in C
    }

    void printList()
    {
        ListNode * temp;
        temp = list;
        while(temp!=0)
        {
            printf("%d->", temp->item);
            temp = temp->next;
        }
        printf("\n");
        printf("Length: %d\n",getLength());
    }

    //------------write code for the functions below-----------
    int insertLast(int item)///task - 07 (making efficient using tail
    {
        //write your codes here
        //effective code here .....bro
        ListNode * lastNode = new ListNode();
        lastNode->item = item;
        lastNode->next = NULL;

        if(tail == 0)//also head == 0 so..
        {
            list = tail = lastNode;
            length++;
            return SUCCESS_VALUE;
        }
        else{
            tail->next = lastNode;
            tail = tail->next;
            length++;
            return SUCCESS_VALUE;
        }
    }

    ListNode * getItemAt(int pos)///task - 08
    {
         //write your codes here
                 //write your codes here
         if(pos > getLength() || pos < 1)return 0;

         ListNode* temp = list;
         for(int i = 1;i<pos;i++){//need to iterate just one less then position
            temp = temp->next;
         }
         return temp;

    }

    int deleteLast()///task - 09
    {
        //write your codes here
        if(list == 0 && tail == 0)return NULL_VALUE;
        else if(list == tail){//only one node
            length--;
            free(list);
            list = tail = 0;
        }
        else{//at least two node
            ListNode * temp = list;
            while(temp -> next != tail){//traversing to beyond last node
                temp = temp->next;
            }
            temp->next = NULL;
            free(tail);

            length--;

            tail = temp;
        }
        return SUCCESS_VALUE;
    }

    //destructor
    ~LinkedListWithTail()//this is for no reason bwt needed here
    {
        //write your codes here
        ListNode* destructor = list;

        while(list != NULL){
            --length;
            list = list->next;
            free(destructor);
            destructor = list;
        }
        list = tail = 0;
        //printf("\nList has been destructed\n");
    }
};







class Queue
{
    LinkedListWithTail ll;
public:
    Queue(){}

    void push(int item)
    {
        //write your codes here
        ll.insertLast(item);
    }

    int pop()
    {
       //write your codes here
       if(ll.getLength() > 0){
            int value = (ll.getItemAt(1))->item;
            ll.deleteItem(value);
            return value;
        }
        else{
            puts("Queue UnderFlow");
            return NULL_VALUE;
        }
    }

    int front(){
        //write your codes here
       if(ll.getLength() > 0){
            int value = (ll.getItemAt(1))->item;
            ///ll.deleteItem(value);
            return value;
        }
        else{
            puts("Queue UnderFlow");
            return NULL_VALUE;
        }
    }

    bool empty(){
        return ll.getLength() == 0;
    }
};








//___________________________________________Adjacency List Part____________________________________
int indx_1, indx_2;
int lastIndx_1[1000], lastIndx_2[1000];

struct AdjList{
    int from, to, weight, prevIndx;
}adjList_1[1000], adjList_2[1000];

void addEdge_1(int& u, int& v, int& w){
    if(indx_1==0){
        memset(lastIndx_1, -1, sizeof(lastIndx_1));
    }
    adjList_1[indx_1].from = u, adjList_1[indx_1].to = v, adjList_1[indx_1].weight = w, adjList_1[indx_1].prevIndx = lastIndx_1[u];
    lastIndx_1[u] = indx_1++;
}

void addEdge_2(int& u, int& v, int& w){
    if(indx_2==0){
        memset(lastIndx_2, -1, sizeof(lastIndx_2));
    }
    adjList_2[indx_2].from = u, adjList_2[indx_2].to = v, adjList_2[indx_2].weight = w, adjList_2[indx_2].prevIndx = lastIndx_2[u];
    lastIndx_2[u] = indx_2++;
}
//___________________________________________________________________________________________________


#define INF (1<<30)

int nodes, edges;
int source, destination;
int cycle = -33;
int dist[1000];
int pred[1000];
bool inQueue[1000];
int pushCounter[1000];
bool isCycleNeg = false;


int bellmanFord(int source, int destination){

    Queue queue1;
    queue1.push(source);
    inQueue[source] = true;//1
    dist[source] = 0;//2
    pushCounter[source]++;//3
    pred[source] = -1;

    while(!queue1.empty() && !isCycleNeg){
        int u = queue1.front();
        queue1.pop();
        inQueue[u] = false;

        for(int e = lastIndx_1[u] ; e != -1 ; e = adjList_1[e].prevIndx){
            int update = dist[u] + adjList_1[e].weight;
            int v = adjList_1[e].to;

            if(dist[v] > update) {

                dist[v] = dist[u] + adjList_1[e].weight;
                pred[v] = u;

                if (!inQueue[v]) {
                    queue1.push(v);
                    inQueue[v] = true;
                    if(++pushCounter[v] > nodes-1){
                        isCycleNeg = true;
                        ///return cycle;
                    }
                }

            }
        }
    }

    return dist[destination];
}


void printPaht(int source, int destination){
    if(source == destination){
        cout<<destination<<" ";
    }
    else{
        printPaht(source, pred[destination]);
        cout<<destination<<" ";
    }

}


void input(){
    cout<<"INPUT: "<<endl;
    cin>>nodes>>edges;
    for(int i = 1; i <= edges; i++){
        int u, v, w;
        cin>>u>>v>>w;
        addEdge_1(u, v, w);
    }
    //write your codes here...

    cin>>source>>destination;
}

void output(){
    cout<<"OUTPUT: "<<endl;
    if(isCycleNeg){
        cout<<"Negative Cycle Detected"<<endl;
        /*//choose graph vertex started with index 1
        for(int i = 1; i <= nodes; i++){
            cout<<"{ node: "<<i<<", push counter: "<<pushCounter[i]<<", dist: "<<dist[i]<<" }"<<endl;
        }*/
    }
    else{
        //choose graph vertex started with index 1
        for(int i = 1; i <= nodes; i++){
            cout<<"{ node: "<<i<<", push counter: "<<pushCounter[i]<<", dist: "<<dist[i]<<" }"<<endl;
        }
        printPaht(source, destination);
    }
}





int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //writes your code here.............

    input();

    isCycleNeg = false;

    for(int i = 0 ; i <= nodes ; i++){
        dist[i] = INF;
        inQueue[i] = false;
        pushCounter[i] = 0;
        pred[i] = -1;
    }

    int res = bellmanFord(source, destination);

    output();

    return 0;
}