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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
