#include <bits/stdc++.h>//!IMPLEMENTING THE DFS AND BFS FOR THE FOLLOWING GRAPH
#include <functional>
using namespace std;
//std::priority_queue<int,vector<pair<int,int> >,greater<pair<int,int> > > minheap;
struct node{int data;
            int weight;
            node*next;};
struct List{node* head;};//! this is the first element of the list to store the address of the linked list of the vertex
struct graph{int noe;List* arr; };//! graph is basically giving us a pointer to the first element of the array of (linked list which stores the address of other vertex)
graph* makegraph(int num)//! function to create the basic body of the graph
{    //!first we need to dynamically allocate an array of linked lists , for storing "num" no. of linked lists of vertex
     List* temparr=new List[num];//!creating an array of the pointers of 1st element of adjacent vertex
    graph* g=new graph;
    g->arr=temparr;
    for(int i=0;i<num;i++)
        temparr[i].head=NULL;//! second we need to dynamical create a linked list of one element point to a NULL pointer
    g->noe=num;
    return g;

}
void add(graph* g,int startvertex,int endvertex,int weight)
{ //!first we need to create a node to store the vertex and the address of the next vertex
    node* newnode=new node;

    //!THE UNDERNEATH STEPS ARE NOTHING SPECIAL BUT JUST ADDING AN ELEMENT TO THE FRONT OF THE LINKED LIST
    newnode->data=endvertex;
    newnode->weight=weight;
    newnode->next=g->arr[startvertex].head;//! making the address of next in node point to the head

    //!since adding an element at the front of linked list takes O(1) time therefore we do so
    g->arr[startvertex].head=newnode;//! now we make our new node the head of the linked list

//!THE UNDERNEATH STEPS NEED TO BE DONE ONLY IN THE CASE OF UNDIRECTED GRAPH
    node* newnode2=new node;
     newnode2->data=startvertex;
     newnode2->weight=weight;
     newnode2->next=g->arr[endvertex].head;
     g->arr[endvertex].head=newnode2;

}


void print(graph*g)
{
for(int i=0;i<g->noe;i++)
   {node*temp= g->arr[i].head;
    cout<<"HEAD "<< i+1<<"::";
   while(temp!=NULL)
       {cout<<"->"<<temp->data+1;
        temp=temp->next;
       }

       cout<<endl;
   }

}

void dijkstra(graph*g, int startvertex)
{ set<pair<int,int> >distindex;
  pair<int,int>start;
  set<pair<int,int> >::iterator it;
  distindex.insert(make_pair(0,startvertex));
  for(int i=1;i<g->noe;i++)
    distindex.insert(make_pair(INT_MAX,i));
  while(!distindex.empty())
  {
   it=distindex.begin();
   start=*it;
   cout<<start.second<<" "<<start.first<<endl;
     distindex.erase(it);
    node* temp=g->arr[start.second].head;
    while(temp)
    { for(it=distindex.begin();it!=distindex.end();it++)
       if(it->second==(temp->data)&&(temp->weight+start.first)<=it->first)
        { distindex.erase(it);
        distindex.insert(make_pair((temp->weight+start.first),temp->data));
          break;
        }
      temp=temp->next;

    }


     }

}



int main()
{
    //!IMPLEMENTING DIJKSTRA
    int num=9;
    graph* g=makegraph(num);
    g->noe=num;



    add(g, 0, 1, 4);
    add(g, 0, 7, 8);
    add(g, 1, 2, 8);
    add(g, 1, 7, 11);
    add(g, 2, 3, 7);
    add(g, 2, 8, 2);
    add(g, 2, 5, 4);
    add(g, 3, 4, 9);
    add(g, 3, 5, 14);
    add(g, 4, 5, 10);
    add(g, 5, 6, 2);
    add(g, 6, 7, 1);
    add(g, 6, 8, 6);
    add(g, 7, 8, 7);

   dijkstra(g, 0);





}