May 2020
1 / 10
May 2020
May 2020
thushar_ke25
May '20
5 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct graph
{
    char city[11];
    int key;
    int cost;
    struct graph *link;
};
struct graph ** UpdateName(struct graph **list,int key,char cityname[10000][11],int n)
{
	struct graph *temp;
    for(int j=0;j<n;j++)
            {
                temp=*(list +j);
                    key=temp->key;
                    strcpy(temp->city,cityname[key-1]);
            }
    return list;
}
struct graph *Create(int key)
{
    char city[11];
    struct graph *newnode;
        newnode=(struct graph *)malloc(sizeof(struct graph ));
        scanf(" %s",city);
        strcpy(newnode->city,city);
        newnode->key=key;
        newnode->cost=0;
        newnode->link=NULL;
    return newnode;
}
struct graph *listofNeighbours(int noOfNeighbours)
{
	struct graph *temp,*last;
    int key,cost;
    struct graph * Neighbourlist=NULL;
    for(int j=1;j<=noOfNeighbours;j++)
        {
            temp=(struct graph *)malloc(sizeof(struct graph ));
            scanf("%d",&key);
            temp->key=key;
            scanf("%d",&cost);
            temp->cost=cost;
            temp->link=NULL;
            if(Neighbourlist==NULL){
                Neighbourlist=temp;
                last=temp;
            }
            else{
            last->link=temp;
            last=temp;
            }
 
        }
        return Neighbourlist;
}
int Min(int dist[10001],int n,int visited[10001])
{
    int minDist=200000,min;
    for(int i=1;i<=n;i++)
    {
        if(dist[i]<minDist)
        {
                if(i!=visited[i])
                {
                	minDist=dist[i];
                	min=i;
                }
        }
    }
    return min;
}
int main()
{
    struct graph **list;
    struct graph *temp,*tempsource,*tempdestination;
    int testcases,noOfCities,key,noOfNeighbours,noOfPaths,distance,min;
    int dist[10001],visitedNodes[10001],keysource,keydestination;
    char source[11],destination[11];
    char cityname[10000][11];
    scanf("%d",&testcases);
 
    for(int t=0;t<testcases;t++){
 
	    scanf("%d",&noOfCities);
	    list=(struct graph **)malloc(noOfCities*sizeof(struct graph *));
	    for(int i=0;i<noOfCities;i++)
	    {
 
	        key=i+1;
	        struct graph *newnode;
	        newnode=Create(key);
	        strcpy(cityname[i],newnode->city);  
 
	        scanf("%d",&noOfNeighbours);
	        newnode->link=listofNeighbours(noOfNeighbours);
	        *(list+i)=newnode;
	    }
	    list=UpdateName(list,key,cityname,noOfCities);
 
	    scanf("%d",&noOfPaths);
	    for(int i=1;i<=noOfPaths;i++)
	    {
	        for(int i=1;i<=noOfCities;i++){
	        dist[i]=200000;
	        visitedNodes[i]=0;
	        }
	        scanf(" %s",source);
	        scanf(" %s",destination);
	        keysource=-1;keydestination=-1;
	        for(int j=0;j<noOfCities;j++)
	        {
	            temp=*(list +j);
	            if(strcmp(temp->city,source)==0){
	            tempsource=temp;
	            keysource=j+1;
	            }
	            else if(strcmp(temp->city,destination)==0){
	            	tempdestination=temp;
	            	keydestination=j+1;
	            }
 
	            if( keysource!=-1&&keydestination!=-1)
	            break;
	        }
	        key=keysource;
	        visitedNodes[key]=keysource;
	        dist[key]=0;
	        temp=tempsource->link;
	        while(temp!=NULL)
	        {
	            distance=dist[key]+temp->cost;
	            if(distance<dist[temp->key])
	            dist[temp->key]=distance;
	            temp=temp->link;
	        }
 
	        min=Min(dist,noOfCities,visitedNodes);
	        while(visitedNodes[keydestination]!=keydestination)
	        {
	            temp=*(list+(min-1));
	            key=temp->key;
	            visitedNodes[min]=min;
	            temp=temp->link;
	            while(temp!=NULL)
	            {
	                if(temp->key==visitedNodes[temp->key])
	                    temp=temp->link;
	                else 
	                {
	                    distance=dist[key]+temp->cost;
	                    if(distance<dist[temp->key])
	                    dist[temp->key]=distance;
	                    temp=temp->link;
	                }
 
	            }
 
	           min=Min(dist,noOfCities,visitedNodes);
	        }
	        printf("%d\n",dist[keydestination]);
	    }
 
 
    }
    return 0;
 
}

  • created

    May '20

  • last reply

    May '20
  • 9

    replies

  • 750

    views

  • 2

    users

  • 1

    like

fyl
May '20

The program you sent doesn’t compile. :confused:

Also: which problem are you working on? It’s interesting to tell us, since its specific border cases might play a role on runtime errors.

thushar_ke25
May '20

sorry,Forgot to update the code,
The problem is “The Shortest Path”.
Thank You in Advance.

fyl
May '20
1

Could you please select the code and press Ctrl+Shift+C before posting?
It makes the entire code preformatted in your post.

It matters because I think we are losing some characters. For example, the line

(dist +i)=200000;

inside your main() would make your code get a compile error.

EDIT: Thank ya. :slightly_smiling_face:

thushar_ke25
May '20

I’ve Updated (I apologize, I didn’t knew how to do that before):smiley:

fyl
May '20
thushar_ke25

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:

  1. 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.
  2. 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.
  3. If you can use vectors instead of linked lists, use vectors. They are more time efficient to navigate.
  4. 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).
thushar_ke25
May '20

Thank you,
I’ve made the changes you mentioned.(It solved my runtime error)
But, unfortunately getting a TLE error as you mentioned.
Tried your solutions.
I think still my code is not good enough.
please can you guide me where can I improve my code.

fyl
May '20

Suppose the input is the largest complete graph under the constraints. How much time would it take to read it and then build your data structures?

For each vertex, you would have to add n-1 neighbors.
Since you are inserting at the end of your linked lists, each neighbor takes time O(n).
So for a vertex, you take O(n^2) time: O(n) neighbors, each one with time O(n).
And for the entire graph, O(n^3). This is too much.

So something you can do is change the way you add a neighbor to a vertex. See if you can find a way to do it in O(1), either by changing the data structure, or by changing the way you are adding it to the list.

If I didn’t overlook anything, I think this is the most important thing that you should look into. Besides that, there are just a bunch of details that might improve your coding skills and reasoning for future problems. Nothing that would substantially deny you an AC in this problem.

There is no need to update the names in the structs under the neighbors lists, since you never actually use this info afterwards. Also: in your code list[i] is always the node with key = i+1, so there’s no real need to check this info as well – the index gives you the key (the same reasoning could be applied in other places, for example, for cityname[i]).

And, for bonus points (I don’t really think you need to go this deep to solve this specific problem, but this might come in handy in the future, when you face harder problems): Your implementation of Dijkstra’s is O(m + n^2), where m is number of edges and n is number of vertices. There is an implementation using heaps that is O(m + n log n), which is better if you don’t have that many edges. This problem can be used to practice this as well.

Hope you get that AC.

thushar_ke25
May '20

Thank you so much
I’ve learnt many things today from your advice.
I’ve applied those changes and added few of my own.(Also I think I inserted neighbours in O(1) time)
but,sadly still getting a TLE error.
Can guide me how to find out which part of my code is responsible for this error.

fyl
May '20
1

Hm. Weird.

Maybe you will have to use Dijkstra with heaps, in the end?

Also try to find a way of not using any malloc. list could be very well a static vector. As for the linked list of neighbors, for each vertex you can store just the indices of the neighbors and their corresponding costs. This can be done for each vertex with two vectors and an int.

And there’s a bug in your code. Consider what happens if you have exactly two cities at distance 200000 from each other.

EDIT: No, you absolutely have to use Dijkstra with heaps. Problem statement says you have distance at most 200000, which means E <= 200000 as well, since each edge has cost at least 1. Since V <= 10000, Dijkstra without heaps takes O(E + V^2) time, which ends up being ~10^8, which is bad. Using heaps, on the other hand, takes O(E + V log V) time, which is ~10^5, and this is manageable. My bad. ):