This is the solution to the MST problem....
m getting WA again n again... cant figure out where's the mistake...
so plzzz help!!!
https://www.spoj.pl/problems/BLINNET/



#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<queue>

#define MAXINT (int)9e9
#define TR(a,it)        for(typeof((a).begin()) it=(a).begin(); it!
=(a).end(); ++it)
using namespace std;

struct node
{
       long int data;
       string name;
       long int cost;
       long int distance;
       long int parent;

       friend bool operator>(const node &a, const node& b);
};

long int prims(vector< list<node> > &adjlist, int n);

int main()
{
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);

     long int n, t, no_neigh;
     cin >> t;
     while(t--)
     {
               vector< list<node> > adjlist;
               node temp;
               getchar();
               cin >> n;
               adjlist.resize(n + 1);
               for(int i=1; i<=n; i++)
               {
                        cin >> temp.name;
                        //temp.data = i;
                        //adjlist[i].push_back(temp);

                        cin >> no_neigh;
                        for(int j=1; j<=no_neigh; j++)
                        {
                                 cin >> temp.data >> temp.cost;
                                 adjlist[i].push_back(temp);
                        }
               }

               /*for(int i=1; i<=n; i++)
               {
                   cout << i << ":" << endl;
                   TR(adjlist[i], it)
                      cout << it->data << " " << it->cost << endl;
               }*/

               cout << prims(adjlist, n) << endl;
     }
}

bool operator>(const node &a, const node& b)
{
     return a.distance > b.distance;
}

long int prims(vector< list<node> > &adjlist, int n)
{
      priority_queue<node, vector<node>, greater<node> > pq;
      node heap[n+1];
      for(long int i=1; i<=n; i++)
      {
            heap[i].data = i;
            heap[i].distance = MAXINT;
            heap[i].parent = -1;
      }

      long int start = 1;
      heap[start].distance = 0;
      pq.push(heap[start]);

      while(!pq.empty())
      {
            node top = pq.top();   pq.pop();
            //cout << "popped :" << top.data << " " << endl;
            if(top.distance <= heap[top.data].distance)
            {
                  //cout << "Traversed " << endl;
                  TR(adjlist[top.data], it)
                  {
                       if(heap[it->data].distance > it->cost)
                       {
                            heap[it->data].distance = it->cost;
                            heap[it->data].parent = top.data;
                            //cout << "Pushed " << it->data << endl;
                            pq.push(heap[it->data]);
                       }
                  }
            }
      }

      long int sum = 0;
      for(int i=1; i<=n; i++)
          sum += heap[i].distance;
      return sum;
}

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Reply via email to