DIJKSTRA  USING  SET  (ADJ. LIST )\\  spoj ques (The shortest path)




Here set  is doing the same job as  of minimum priority queue..
Set also arrange the in ascending order.



#include<bits/stdc++.h>
#define pp pair<int,int>

using namespace std;

void dijk(int src,int des,int nc,vector<pair<int,int> > v[])
{
 int i,j,u;
 set<pair<int,int> > Q;
 set<pair<int,int> > :: iterator itx;

   int dist[nc]; for(i=0;i<nc;i++) dist[i]=INT_MAX;

 dist[src]=0;
 Q.insert(pp(dist[src],src));

    while(!Q.empty())
    {
        itx=Q.begin();
        u = itx->second;
        Q.erase(itx);                    ///jo visited ho gaya wo poped

       if(itx->first<= dist[u])
        {
           for(j=0;j<v[u].size();j++)
           if((dist[u]+v[u][j].second)<dist[v[u][j].first])
            {
            dist[v[u][j].first]=dist[u]+v[u][j].second;
            Q.insert(pp(dist[v[u][j].first],v[u][j].first));
            }
        }
    }
cout<<dist[des]<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
 int t;
 cin>>t;
 while(t--)
 {
  int nc,i,j,ci,cc,num,q;
   string s;
   cin>>nc;

   vector<pair<int,int> > v[nc];

   map<string,int> mp1;   ///map ka pahla wala index hota hai
   for(i=0;i<nc;i++)
   {
     cin>>s;
     mp1[s]=i;
     cin>>num;

      for(j=0;j<num;j++)
      {
          cin>>ci>>cc;
          ci--;
          v[i].push_back(make_pair(ci,cc));
      }
   }

   cin>>q;
   for(int k=0;k<q;k++)
   {
    string s1,s2;
    cin>>s1>>s2;
    dijk(mp1[s1],mp1[s2],nc,v);
   }

   for(i=0;i<nc;i++)
    v[i].clear();
   mp1.clear();
 }
return 0;
}

Comments

Popular posts from this blog

Divide Intervals Into Minimum Number of Groups

B. Dreamoon and WiFi :calculate no. of ways : recursive solution (branch and bound )

A. Dreamoon and Stairs : minimum steps to reach : recursion solution.