Hey anyone Plzzzz help... its clearly written code and algo u know vry well so it wont take much time :)
On Jul 5, 8:43 pm, KK <[email protected]> wrote: > 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.
