1. solved it....now its exceeding the time limit...
is my way of graph construction and traversal not the best one..... can it be bettered some way...please help

2. what else you have added?
check here:

Code:
```void Graph::Build_Network()

{
:
:
ListNode *nodePtr = NULL;
ListNode *downPtr = NULL;

while(nodePtr)  //continue through all vertices
{
if(nodePtr->name==v1[j])
break;
else
nodePtr=nodePtr->next; //!!!!!!!!!!!!!!!!!!!! this is will be OK because you check first with while (nodePtr)
}

ListNode *downNode = NULL;
downNode = new ListNode;
downNode->name = v2[j];
// downNode->w=elements[j];
:
:
}```
this is a culprit...

may be you check first,
Code:
```if (nodePtr)
i runned in debug, and always crash here!

see part with "//!!!!!!!!!!!!!!!!!!!!!!!!"

3. well aurilus u say that nodePtr will be null at that point...
but i dont think
because
Code:
``` while(nodePtr)  //continue through all vertices

{

if(nodePtr->name==v1[j])
break;
else
nodePtr=nodePtr->next;
}```
even if v1[j] is the last element in the list then i will break ,.... i dint increment nodePtr=nodePtr->next;
so it wont be null....
but whwre s it breaking...i am still puzzled
i may be wrong
well i have not solved the issue til now

4. Originally Posted by dpp
even if v1[j] is the last element in the list then i will break ,.... i dint increment nodePtr=nodePtr->next;
so it wont be null....
What if none of the vertices have name == v1[j]? If that condition is logically possible, you should write something like this:
Code:
```while (nodePtr && nodePtr->name != v1[j])
{
nodePtr = nodePtr->next;
}

if (nodePtr)
{
ListNode *downNode = NULL;
downNode = new ListNode;
downNode->name = v2[j];

// ...
}
else
{
// v1[j] is not in the list.
// Print a message to inform the user, throw an exception, etc.
}```
If that condition is logically impossible, use an assertion to document the fact, e.g.,
Code:
```while (nodePtr && nodePtr->name != v1[j])
{
nodePtr = nodePtr->next;
}

assert(nodePtr && "No vertex has the given name!");

ListNode *downNode = NULL;
downNode = new ListNode;
downNode->name = v2[j];

// ...```
In this case it does seem possible, even probable, that the user could provide a name that does not correspond to any vertex, so I would choose the former.

Oh, and you need to break up your function into smaller ones.

5. well i need not take care of tat case...its with the assumption that v1 belongs to one of the nodes in nodeptr....

it can never violate it

6. well auralius can u check with this please ...if its crashing wen u run..
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>
#include<map>

using namespace std;

//template < class Key, class Compare = less<Key>,
//      class Allocator = allocator<Key> > class multiset;

# define maxedges 300009
# define maxnodes  2059
long long int price=0;

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;

};

public:

Graph() //Constructor

{

}

////////////////////

/////////////////

void Build_Network(); //This function will prompt the user for all of the information, as well as perform the necessary linked list operations

//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;
ListNode *newNode = NULL;  //This is the new vertex

ListNode *nodePtr = NULL;   //Traversing pointer

ListNode *downPtr = NULL;  //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];

std::map<long long int, long long int> v1,v2;

static long long int  state[maxnodes],sum=0,v=0;
static long long count=0,flag=0;

if(!myset.empty())
myset.clear();

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

else

{

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;

ListNode *nodePtr = NULL;
ListNode *downPtr = NULL;

while(nodePtr)  //continue through all vertices

{

if(nodePtr->name==v1[j])
break;
else
nodePtr=nodePtr->next;
}

ListNode *downNode = NULL;
if (nodePtr)

downNode = new ListNode;

downNode->name = v2[j];

downNode->down = NULL;
downNode->next = NULL; //!!!!!!!!!

{

nodePtr->down = downNode;

}

else

{

while(downPtr->down)

downPtr = downPtr->down;

downPtr->down = downNode;

}

///////// for undirected

/* while(nodePtr)  //continue through all vertices

{

if(nodePtr->name==v2[j])
break;
else
nodePtr=nodePtr->next;
}

ListNode *downNode1 = NULL;
if (nodePtr)

downNode1 = new ListNode;

downNode1->name = v1[j];

downNode1->down = NULL;
downNode1->next = NULL; //!!!!!!!!!

{

nodePtr->down = downNode1;

}

else

{

while(downPtr->down)

downPtr = downPtr->down;

downPtr->down = downNode1;

}*/

}

// }

long long int n;
sum=0;
while(myset.size())
{
s15:

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:

while(nodePtr)
{
////////////////

//////////////
if(nodePtr->name==v)
{

downPtr = nodePtr->down;

while(downPtr) // continue through all Adjacent edges/vertices

{

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<<price*sum<<"\n";

}

///////////////

////////////////

int main()
{
long long int t,n;

cin>>t;
while(t)
{

cin>>price;
Graph s;
s.Build_Network();

t--;

}

return 0;
}```

i dint use the dsestroy fns given by u...instread i use delete operation...guess this will do... wen i used destroy i was able to see it crashing....

7. Yes...
See below
Code:
```while(nodePtr)  //continue through all vertices
{

if(nodePtr->name==v1[j])
break;
else
nodePtr=nodePtr->next;
}

ListNode *downNode = NULL;

if (nodePtr)                  //!!!!!!!!!!!! You added this as per my first suggestion, right?
down_head =nodePtr->down; //!!!!! Now, it's safe, but........

downNode = new ListNode;

downNode->name = v2[j];

downNode->down = NULL;

downNode->next = NULL;

{

nodePtr->down = downNode; //!!!!!!!!!!!!!!!!!!!!! crash here! why...??

}

else```
i think i can conclude that your common problem is due to a careless pointer assignment...
Code:
`nodePtr->down = downNode`
how if i ask: what will happen if nodePtr is NULL...
well, easy, its nodePtr->down will be pointing to invalid location on memory...
see...!!!
but you then assign downNode to it...

my suggestion, go through all your function...
be careful when you assigned to or from
blabla->down or blabla->from
because if blabla is NULL then its blabla->down or blabla->from will be pointing to invalid location on memory...(as i said before)...

cheers

8. thanks ...u mean to say
Code:
```if(nodePtr)
{
nodePtr->down = downNode; //!!!!!!!!!!!!!!!!!!!!! crash here! why...??
}```
fine... but i am puzzled with one big thing...when will i have my nodePtr null...

assume that the user i/p's are all safe....how will my nodeptr point to null...or where is it pointing to null

9. Originally Posted by dpp
how will my nodeptr point to null...or where is it pointing to null
Code:
```while(nodePtr)  //continue through all vertices
{

if(nodePtr->name==v1[j])
break;
else
nodePtr=nodePtr->next;
}```
when you leave the while loop without entering if even once - what is the value of nodePtr?

10. i know that ...but it wont exit the while loop without entering if

11. Originally Posted by dpp
i know that ...but it wont exit the while loop without entering if
It might. Even if you claim that the input is guaranteed to be correct, you should still check for it. At the very least you should use an assertion to document your assumption, as I stated, but an assertion is not really the best tool for that since it means that invalid user input in a release build would result in undefined behaviour whereas invalid user input in a debug build will trigger an assertion failure.

12. but laserlight my question is ..Is it only because of user's bad i/p tat crash will occur???

13. Originally Posted by dpp
Is it only because of user's bad i/p tat crash will occur?
In that particular case, I am inclined to say yes, but it would help if you indented your code more consistently and separated it into smaller functions. However, you apparently have other problems lurking in your code.

14. Originally Posted by dpp
but laserlight my question is ..Is it only because of user's bad i/p tat crash will occur???
There is no such ting as bad user input - user could enter anything.