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;
}
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
Post a Comment