Friday, 23 January 2015

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;
}

No comments:

Post a Comment