TLE in tourmap

general
,
1

why this code for TOURMAP has TLE???
please point out the cause…

#include <stdio.h>
#include <string.h>
char edgefrom[5002][52],edgeto[5002][52];
int cost[5005],forward[5005];
int sum=0;
int main()
{
    int t,i,n,mark,flag=1,l=0,j,a,k;
    char temp[20];
    scanf("%d",&t);
    //printf("%d\n",t);
    while(t--)
    {
        sum=0;
        a=0;
        scanf("%d",&n);
        for(j=0;j<n-1;j++)
        {
            a=0;
            forward[j]=-1;
        scanf("%s%s%s",edgefrom[j],edgeto[j],temp);
        l=strlen(temp);
        for(k=0;k<l-1;k++)
        a=a*10+(temp[k]-'0');
        sum+=(cost[j]=a);
        }
       for(i=0;i<n-1;i++)
        {
            for(j=0;j<n-1&&(strcmp(edgefrom[i],edgeto[j]));j++){}
        if(j==n-1)
        {
            mark=i;
        }
        else
         {
             forward[j]=i;
         }
        }
        k=mark;

         for(j=0;j<n-1;j++)
        {
            printf("%s %s %d$\n",edgefrom[k],edgeto[k],cost[k]);
            k=(forward[k]);
        }
        printf("%d$\n",sum);
       // fflush(stdin);
        //printf("\n");
    }
    return 0;
  }

**OR you can view my submission at link here **`


[1]


  [1]: http://www.codechef.com/viewsolution/1554691
3 Likes
2

I edited your code tags which were broken…

At first sight, it seems that you are trying to implement the editorial’s approach, which is a good thing to do, so you can learn and improve, and apparentely, it’s not something the majority of people does, so, kudos for that…

Regarding the code itself, I would say that your nested for loops can be a possible cause for TLE…

I have to say that I still need to work around the graph solution modellation a bit better to fully understand it, but I would suggest you to use a custom data structure that does the same job as map and/or set difference, so you can easily retrieve all the cities once you have the 1st one determined…

Key idea I used:

Construct 2 arrays (one with the 1st cities and another with the second cities);

Eliminate all common entries on both arrays and retrieve the entry from the first cities array: this will be the 1st city;

Next use a mapping to connect cities, like:
map[city1] = city2; (this can be done while processing input)

Next use a loop to determine the tour;

If you want you can see my solution as a reference of this exact approach:
http://www.codechef.com/viewsolution/1523615

Hope you can convert it to C easily

1 Like
3

thanks @kuruma…i will change it to C

4

your code can be implement in JAVA using hashmap

1 Like
5

Yes, Java hashmap data structure allows for the exact same implementation to be done in Java as the one that was done in C, :wink:

Bruno

1 Like