www.spoj.pl/problems/BLINNET/
Here is the code for the same... Its not getting AC in SPOJ
m not able to figure out wheres the hole in this... plzz help
#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(long int i=1; i<=n; i++)
{
cin >> temp.name;
//temp.data = i;
//adjlist[i].push_back(temp);
cin >> no_neigh;
for(long 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;
pq.push(heap[it->data]);
}
}
}
}
long int sum = 0;
for(int i=1; i<=n; i++)
sum += heap[i].distance;
return sum;
}
/*
Input:
2
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
3
ixowo
2
2 1
3 3
iyekowo
2
1 1
3 7
zetowo
2
1 3
2 7
Output:
3
4
*/
--
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.
