thanks laserlight...i am thru with it.
well am getting runtime error...(its not seg fault.. so says an online judge system )
http://www.spoj.pl/forum/viewtopic.p...af7bef1a4#p103
i had "other" runtime error. this is for spanning tree prim's algo
Code:
#ifndef GRAPH_H //This checks the preprocessor to see if GRAPH_H has been defined and if it hasnt then it defines it as follows.
#define GRAPH_H
#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include<map>
using namespace std;
# define maxedges 300000
# define maxnodes 10009
class Graph
{
private:
struct ListNode
{
long long int name;
struct ListNode *next; //This creates the same ListNode structure for the next and down pointers each one will have a name, a next, and a down.
struct ListNode *down;
};
ListNode *head;
ListNode *down_head;
public:
Graph() //Constructor
{
head = NULL; //in-line initializations of head and down_head
down_head = NULL;
}
void Build_Network(); //This function will prompt the user for all of the information, as well as perform the necessary linked list operations
void Display(); //This function will print out the linked list in a manner that is easily read.
};
#endif //Ends the definition of GRAPH_H
void Graph::Build_Network()
{
//multiset<int> myset;
//multiset<int>::iterator it,itlow,itup;
multiset<int> myset;
multiset<int>::iterator it,itlow,itup;
ListNode *newNode; //This is the new vertex
ListNode *nodePtr; //Traversing pointer
ListNode *downPtr; //Edge/Adjacent Vertex Traversing pointer
long long int num_Nodes,vertex,alt;
long long int i=0,j=0;
long long int V_Name[maxnodes],key[maxnodes],p[maxnodes];
static long long int elements[maxnodes][maxnodes];
static long long int v1[maxedges],v2[maxedges];
//static long long E_Name[5*maxedges];
static long long int state[maxnodes],sum=0,v=0;
static long long count=0,flag=0;
// std::map<long long int, long long int> elements;
myset.empty();
// cout << "How many nodes in the graph?: ";
scanf("%I64d",&num_Nodes);
//cin>>num_Nodes;
long long int num_Edges;
//cout << "How many Edges are connected to ";
// cin >>num_Edges;
scanf("%I64d" ,&num_Edges);
for( i = 0; i<num_Nodes; i++)
//ifor
{
V_Name[i]=i+1;
if(i==0)
key[V_Name[i]]=0;
else
key[V_Name[i]]=maxedges+maxedges+i;//1000000
//q.push(key[V_Name[i]]);
myset.insert(key[V_Name[i]]);
p[V_Name[i]]=0;
state[V_Name[i]]=0;
newNode = new ListNode;
newNode->name = V_Name[i];
newNode->next = NULL;
newNode->down = NULL;
// Building the Vertex List
if(!head)
head = newNode;
else
{
nodePtr = head;
while(nodePtr->next)
nodePtr = nodePtr->next;
nodePtr->next = newNode;
}
}//endifor
for( j=0; j<num_Edges; j++)
//jfor
{
// cout << "What is the name of edge "<< j+1 << "?: ";
scanf("%I64d" ,&v1[j]);
scanf("%I64d" ,&v2[j]);
scanf("%I64d" ,&alt);
//elements[v1[j]+v2[j]+v1[j]*v2[j]]=alt;
elements[v1[j]][v2[j]]=0;
elements[v2[j]][v1[j]]=0;
elements[v1[j]][v2[j]]=alt;
elements[v2[j]][v1[j]]=alt;
// cin>>v1[j]>>v2[j]>>E_Name[v1[j]+v2[j]+(v1[j]*v2[j])];
// cout<<"\n e_name"<<E_Name[5];
ListNode *nodePtr;
ListNode *downPtr;
nodePtr = head;
while(nodePtr) //continue through all vertices
{
if(nodePtr->name==v1[j])
break;
else
nodePtr=nodePtr->next;
}
ListNode *downNode;
down_head =nodePtr->down;
downNode = new ListNode;
downNode->name = v2[j];
// downNode->w=elements[j];
downNode->down = NULL;
//Building the Adjacent Vertex List
if(!down_head)
{
nodePtr->down = downNode;
down_head = downNode;
}
else
{
downPtr = down_head;
while(downPtr->down)
downPtr = downPtr->down;
downPtr->down = downNode;
}
///////// for undirected
nodePtr=head;
while(nodePtr) //continue through all vertices
{
if(nodePtr->name==v2[j])
break;
else
nodePtr=nodePtr->next;
}
ListNode *downNode1;
down_head =nodePtr->down;
downNode1 = new ListNode;
downNode1->name = v1[j];
downNode1->down = NULL;
//Building the Adjacent Vertex List
if(!down_head)
{
nodePtr->down = downNode1;
down_head = downNode1;
}
else
{
downPtr = down_head;
while(downPtr->down)
downPtr = downPtr->down;
downPtr->down = downNode1;
}
}
// }
long long int n;
sum=0;
while(myset.size())
{
nodePtr = head;
it=myset.begin();
n=*it;
sum+=n;
if(myset.size()==1)
{
goto s12;
}
for(i=0;i<num_Nodes;i++)
{
if(key[i+1]==n)
{
v=i+1;
goto s11;
}
}
s11:
state[v]=1;//to know its not in queue
myset.erase(it);
key[v]=-1;
s10:
nodePtr=head;
long long counter=0;
long long altcounter=0;
while(nodePtr)
{
////////////////
counter=0;
altcounter=0;
//////////////
if(nodePtr->name==v)
{
counter=0;
altcounter=0;
downPtr = nodePtr->down;
while(downPtr) // continue through all Adjacent edges/vertices
{
/*altcounter++;
cout<<"\n are :ADJ----"<<downPtr->name;
cout<<"\nstate is "<<state[downPtr->name];
if(state[downPtr->name]!=0)
counter++;*/
if((state[downPtr->name]==0)&&(elements[v][downPtr->name]<=key[downPtr->name]))
{
//
p[downPtr->name]=v;
it= myset.find(key[downPtr->name]);
key[downPtr->name]=-1;
myset.erase(it);
key[downPtr->name]=elements[v][downPtr->name];
myset.insert(key[downPtr->name]);
}
downPtr = downPtr->down; //Increment the Adjacency pointer
}
it=myset.begin();
}//if==n
nodePtr = nodePtr->next;
}//while nodeptr
}//while q empty
s12:
//cout<<"\nPRICE IS"<<price<<"\n";
printf("%I64d" ,sum);
printf("\n");
// delete nodePtr,downPtr;
}
///////////////
////////////////
int main()
{
long long int t,n;
cin>>t;
while(t)
{
Graph s;
s.Build_Network();
t--;
}
return 0;
}
can u help me
thanks
i ve posted the entire code