OJ Board

Posted: **Sat Jan 04, 2003 10:35 pm**

I just started to try graph related problems, and I got stuck on the first problem... this one. I took a pretty brute force, backtracking based approach, once arriving at a city, going to every linked one, recursively (isn't it what depth-first search is all about?).
My solution is giving the right answers for the sample input (OK, I know that they are easy), but once submitted I get TL
I just want to know if anyone got AC with backtracking, or should I start to look for some other approach?

thanx in advance :)

Posted: **Sat Jan 04, 2003 11:12 pm**

This is a fairly typical graph problem [if such a thing exists

]. Try looking at some well-known graph algorithms such as Dijkstra's Algorithm, Kruskal's Algorithm, or Prim's Algoirithm to get some ideas for a more efficient approach - you should have no trouble solving the problem in under 1 second.

If you are still having trouble with this problem, you may want to try some easier graph problems first. For example, problem 459 can be solved with a simpler algorithm (that is very similar to the one that you described).

Posted: **Sat Jan 14, 2006 5:31 pm**

hi, i am also getting tle. i used floyd-warshall maximin distance. and i used binary search tree for string searching. can't it be run within time limit applying these methods? here n can be as big as 200. and my program is O(n^3), is it acceptable?

Posted: **Sat Jan 14, 2006 6:45 pm**

Your complexity .. O(n^3) which in worst case can result in about 8 x 10^6 iterations may be (or may not be) good enough for this problem. But as each of iterations also requires a search and a number of string compares the complexity actually rises by a factor that can get u TLE.

Here is how I solved the problem:

Represented each city by an integer for example say .. "Stuttgart" is represented by node 1 and "Ulm" is represented by 2. Then I try to find the shortest path between 1 and 2 instead of Stuttgart and Ulm. This I believe reduces the practical complexity of the problem, as I dont need string comparison in the main iterative portion of the problem. Applying Floyd Warshall along with this indexing SHOULD (I havent tested it myself though ) get u AC.

You actually dont need to use ALL PAIR SHORTEST PATH algorithm such as Floyd Warshall in this problem. Because u are given a single pair of cities for a single scenario. Finding the shortest path between all pairs is completely unnecessary, rather you can go for single source shortest path algorithm such as Dijkstra which will reduce the runtime significantly (using priority queue the complexity is O(nlogn) and without using PQ O(n^2) )

Hope it helps

Posted: **Sat Jan 14, 2006 7:32 pm**

After reading ayon's post I have just solved this using Floyd Warshall. Djikstra would be faster I think. My timing isn't one of the fastests but less than half a second. So I'll take it. Moreover I used STL which is thought to be slow. ayon, What do you do before BST? Another problem may be input processing.

Solaris wrote:Then I try to find the shortest path...

There is nothing like shortest path. This problem is similar to 10048 - Audiophobia.

Posted: **Sat Jan 14, 2006 7:49 pm**

You're right mamun. Before my previous post I just checked my old code, it had the function Dijkstra and also ayon mentioned floyd-warshall, and I thought that it was actually a shortest path problem

Sorry for my misleading post. Dijkstra without priority queue is quite fast though (around 0.05 seconds).

The actual problem is a modification of basic shortest path problem.

Posted: **Sun Jan 15, 2006 11:21 am**

hmm, thank you all, i can use dijkstra, but now i know this problem can be solved using floyd-warshall. then why am i getting tle? i didnt use STL, i didn't compare strings in my O(n^3) loops.
here goes my code: to understand my code, i can tell you that, here insert() function return 1 after inserting, and if the string already exist the function return 0, and of course i represented each city by a number(k). i guess i didnt do anything wrong in input processing.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct rec
{
	char s[35];
   int n;
   struct rec *left;
   struct rec *right;
} node;

node *head;

int min(int a, int b)
{
	return a < b? a : b;
}

int max(int a, int b)
{
	return a > b? a : b;
}

int insert(char s[], int k, int &i)
{
	node *T;
   T = head;
   if(head == NULL)
   {
   	head = new node;
      T = head;
   }
   else
   for(;;)
   {
   	if(strcmp(s, T->s) == 0)
      {
      	i = T -> n;
      	return 0;
      }
		if(strcmp(s, T->s) < 0)
      {
      	if(T -> left == NULL)
         {
         	T -> left = new node;
            T = T -> left;
            break;
         }
      	T = T -> left;
      }
      else
      {
      	if(T -> right == NULL)
         {
         	T -> right = new node;
            T = T -> right;
            break;
         }
      	T = T -> right;
      }
   }
   strcpy(T -> s, s);
   T -> n = k;
   T -> left = T -> right = NULL;
   i = k;
   return 1;
}

void freeBST(node *T)
{
	if(T == NULL)
   	return;
   freeBST(T -> left);
   freeBST(T -> right);
   free(T);
}

void main()
{
	int i, j, k, l, n, r, set = 0, d, load[201][201];
   char s1[32], s2[32];
	for(;;)
   {
   	scanf("%d%d", &n, &r);
      if(n == 0 && r == 0)
      	break;
      k = 0;
      memset(load, -1, sizeof(load));
      for(i = 0; i < n; ++i)
      	load[i][i] = 0;
      head = NULL;
      for(i = 0; i < r; ++i)
      {
      	scanf(" %s %s%d", s1, s2, &d);
			if(insert(s1, k, i))
         	++k;
         if(insert(s2, k, j))
         	++k;
         load[i][j] = load[j][i] = d;
      }
      for(l = 0; l < n; ++l)
       	for(i = 0; i < n ;++i)
           	for(j = i; j < n; ++j)
              	load[i][j] = load[j][i] = max(load[i][j], min(load[i][l], load[l][j]));
      scanf(" %s %s", s1, s2);
      insert(s1, 0, i);
      insert(s2, 0, j);
      printf("Scenario #%d\n%d tons\n\n", ++set, load[i][j]);
      freeBST(head);
   }
}

Posted: **Sun Jan 15, 2006 11:52 am**

A typo mistake in inputting.

Code: Select all

      for(i = 0; i < r; ++i) 
      { 
         scanf(" %s %s%d", s1, s2, &d); 
         if(insert(s1, k, i)) 
            ++k; 
         if(insert(s2, k, j)) 
            ++k; 
         load[i][j] = load[j][i] = d; 
      }

You're using the same variable, i for controlling the loop as well as indexing s1.

Posted: **Sun Jan 15, 2006 2:32 pm**

ah, thanks mamun vai. i got accepted in 0.156 sec. that was a stupid mistake. i was wondered, why i was getting tle with vertices at most 200. but i could not find the mistake. it's very easy to use floyd-warshall than other graph algorithms, so i use this algorithm often for small inputs.

Posted: **Sun Nov 05, 2006 12:05 pm**

I try to solve this problem, but always WA !!
Can anyone of you give me some critical IO ???

Thanks in advance ~~

Posted: **Thu Apr 26, 2007 8:16 pm**

can anybody help me???

i got CE, but i run well in my compiler..
thx..

Code: Select all

delete after AC..

Posted: **Fri Apr 27, 2007 3:51 am**

Here..

albet_januar wrote:can anybody help me???

i got CE, but i run well in my compiler..
thx..
Code: Select all
   char input[ 1000 ], fr[ 100 ], to[ 100 ], bil[ 100 ], ;

Posted: **Sat Apr 28, 2007 5:35 pm**

thx.. i got my mistake..
Gbu..

Posted: **Tue Jul 03, 2007 12:59 pm**

I was solving using the binary search (for weight of cargo) and then searching the path in the graph between these two cities. But it's giving WA. I think it is because my program gives answer +/- 1 to the right. Or is not? Can you have a look at binary search fragment of my code plz:

Code: Select all

    while (abs(w1-w2)>1) do
    begin
        w := (w1+w2) div 2;

Posted: **Tue Jul 03, 2007 2:45 pm**

well, i understood. I had to make additional checking after the search to decide what to take: X or X-1.

OJ Board

544 - Heavy Cargo

544 - Heavy Cargo