Since city names are 10 characters long, you actually need 11 chars
to store them. (10 for the characters of the name + 1 for end-of-string, i.e., '\0'
)
In line 91, you have char cityname[noOfCities][10]
. This doesn’t do what I think you want it to do. At compile time, the compiler reads this and allocates some static space for this matrix. Since this is done at compile time (and not during execution), we don’t really know what value was in noOfCities
, so we don’t know how much space was actually allocated either. You should have used malloc
instead.
There are a few ways to make cityname
behave like a matrix programming-wise. You can, for example, do
char **cityname = (char**) malloc(noOfCities * sizeof(char*));
for(int i=0; i<noOfCities; i++)
cityname[i] = (char*) malloc(11 * sizeof(char));
or even better,
char **cityname = (char**) malloc(noOfCities * sizeof(char*));
char *memcityname = (char*) malloc(noOfCities * 11 * sizeof(char*));
for(int i=0; i<noOfCities; i++)
cityname[i] = memcityname + i*11;
which saves some time from all those malloc
calls.
Since we are respecting good practice, don’t you forget to free
everything you malloc
-ed eventually.
There are, of course, better ways to handle all those mallocs
since we are in a competitive programming context, but I think this would give you less changes to make, given your current code.
On UpdateName
, parameter cityname
is of type char[4][11]
, which messes up all the pointer arithmetics. This is troublesome. Make it char**
instead.
Shouldn’t line 67 be for(int i=1; i<=n; i++)
?
You should either initialize visitedNodes
with zeroes or keep track of how many values are in there. There are loops in your code that might access undefined values and you must assume that uninitialized values may not be by default zero.
There are many other optimizations and little tweaks that could make your code more readable or less error-prone. For example, it’s easier to read/write point[index]
instead of *(point+index)
. And they are equivalent. But there are so many of them to tackle on I don’t think I can manage that.
Anyways, if these changes get your code to work, I think you might get a TLE. If so, you ought to rethink your data structures, since they are inefficient. There’s a potential triple nested loop hidden there that would take O(number_of_cities^3) time to compute, and that’s bad, since number_of_cities <= 10^4.
Things you could consider, in this sense:
- You know how many cities are there at most. It is a given from the problem statement. So you know the max size to many of your vectors, as well as dimensions to your matrices. Use this to your advantage.
- If you can declare a static vector, even if it’s larger than you need for some instances, do it. It’s more time-efficient than
malloc
.
- If you can use vectors instead of linked lists, use vectors. They are more time efficient to navigate.
- Instead of having a list of visited nodes, have a vector
v
of size noOfCities
such that v[i] == 1
if node i
has been visited and 0
otherwise. This gives you this info in O(1).