Thursday, 17 September 2015

all destination shortest path using dijkestra and priority queue



#include <iostream>
using namespace std;
#include<bits/stdc++.h>
typedef long long int lli;
int visited[10010];
lli dist[10010];
#define pp pair<int,int>
// comparator for min heap
class Prioritize
{
public:
    int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 )
    {
        return p1.second > p2.second;
    }
};

int main()
{
    int t;
     cin>>t;
      while(t--)
       {
        list<pair<lli,lli> >li[10010];
        lli n,m;
 
       cin>>n>>m;
       
          for(int i=0;i<m;i++)
           {
            lli a,b,c;
             cin>>a>>b>>c;
            li[a].push_back(make_pair(b,c));
            li[b].push_back(make_pair(a,c));
           
           }
         
             

            for(int i=1;i<=n;i++)
             {
              visited[i]=0;
              dist[i]=INT_MAX;
}


//  declaring pq;
            priority_queue<pp, vector<pp > , Prioritize > q;
           dist[1]=0;
       
           lli ans=0;
           int f=0;
           // need to find distance of all node from 1
           lli start=1;
           q.push(make_pair(1,0));
           while(!q.empty())
            {
           
   
            list<pair<lli,lli> > :: iterator it;
            lli start=q.top().first;
         
           
             q.pop();
            if(visited[start]==1) continue;
            visited[start]=1;
         
            for(it=li[start].begin();it!=li[start].end();it++)
             {
       
              if(!visited[it->first]  && dist[it->first]>dist[start]+it->second)
              {
             
               q.push(make_pair(it->first,dist[start]+it->second));
             
                dist[it->first]=dist[start]+it->second;
              }
             
             }
             
}
               

           
           for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
         }
         return 0;
       }
     
     

No comments:

Post a Comment