Page 2 of 4

Posted: Fri Jan 14, 2005 3:04 pm
by Eduard
I got AC.Don't need test data. :D
Eduard.

Wrong answer.

Posted: Tue Jan 18, 2005 12:42 pm
by Ndiyaa ndako
As far as I know, the Floyd Warshall algorithm computes also the transitive closure of a graph. That means that if D(i,j) is finite in the final adjacency matrix, then there exists a path between the vertex i and j of the graph.

I deduce that if in the final matrix there is an entry with my tag for infinite then there is a pair of cities such that you cannot travel from one to the other.

Code: Select all

 conected = 1;
 ....
 // The graph and the closure have been updated by the Floyd-Warshall
 // algorithm up to this point.
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   conected = conected && closure[i][j];
 if(!conected)
  return -1.0;

 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   if(graph[i][j]>max&&(i!=j))
    max = graph[i][j];
I check that but I still get "Wrong Answer". What's wrong?

Posted: Wed Jan 19, 2005 9:43 am
by sohel
Your method seems to be correct..
.. but the problem might occur during floating point comparison.

How do you check whether the distance between two nodes is less than or equal to 10 ?

Posted: Wed Jan 19, 2005 2:10 pm
by Larry
How do you do the Floyd/Warshall? Do you assume f(a,a) is true?

My method.

Posted: Wed Jan 19, 2005 7:33 pm
by Ndiyaa ndako
The closure matrix is of integer type.

To determine if two vertices are conected I check if the square of their distance is less or equal than 100 with integer arithmetic. After that I store in the adjacency matrix the square root of the number. The tag for infinite is -1.

Code: Select all

 for(k=0;k<n;k++)
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    {
       if(!clausura[i][j])
        clausura[i][j] = clausura[i][k]&&clausura[k][j];
       if(grafo[i][k] >= 0 && grafo[k][j] >= 0 && grafo[i][j] < 0)
         grafo[i][j] = grafo[i][k] + grafo[k][j];
       if(grafo[i][k] >= 0 && grafo[k][j] >= 0 && grafo[i][j] >= 0)
        if(grafo[i][k] + grafo[k][j] < grafo[i][j])
         grafo[i][j] = grafo[i][k] + grafo[k][j];
    }
I have tried that code with both the cases i==j and i != j.

Posted: Wed Jan 19, 2005 9:53 pm
by Monsoon
I think that your implementation of Floyd-Warshall algorithm is wrong. Becouse you should create matrix [1..n,1..n,1..n]. And it should looks like this

Code: Select all

grafo[k-1][i][j] = grafo[k-1][i][k] + grafo[k-1][k][j]; 
ofcourse you can reduce the matrix to [1..2,1..n,1..n].

Maybe i'm wrong, i don't why you use closure??

Posted: Thu Jan 20, 2005 3:31 am
by Larry
Monsoon, you don't need that. A two dimension array is enough.

You can send me your code and I'll check it.

Posted: Sat Feb 05, 2005 6:25 am
by Ndiyaa ndako
I got it accepted: it was an stupid error about the output format.

Thanks everybody.

Posted: Sun Feb 20, 2005 12:30 pm
by murtaza
Can any one point out the bug in the code ....


#include<stdio.h>
#include<math.h>

#define INF 999999999

int grid[101][2];
float gph[101][101];

float floydWarshal( int );


main( )
{
int cases,towns,i,j,m,tmp;
float len;
scanf( "%d", &cases );
for( i = 0;i < cases;i ++ )
{
scanf( "%d", &towns );
for( j = 0;j < towns; j ++ )
scanf( "%d %d", &grid[j][0], &grid[j][1] );
for( j = 0;j < towns;j ++ )
for( m = 0;m < towns;m ++ )
gph[j][m] = INF;
for( j = 0;j < towns;j ++ )
for( m = 0;m <= j;m ++ )
{
tmp = (grid[j][0]-grid[m][0])*(grid[j][0]-grid[m][0])+(grid[j][1]-grid[m][1])*(grid[j][1]-grid[m][1]);
if(tmp <= 100 )
gph[j][m] = gph[m][j] = sqrtf( (float)tmp );
}
printf( "Case #%d:\n", i+1 );
len = floydWarshal( towns );
if( len == -1 )
{
printf( "Send Kurdy\n" );
}
else
printf( "%.4f\n", len );
printf( "\n" );
}
}

float floydWarshal( int towns )
{
int i,j,k;
float max;
for( i = 0;i < towns;i ++ )
for( j = 0;j < towns;j ++ )
for( k = 0;k < towns;k ++ )
{
if( gph[j] > (gph[k] + gph[k][j]) )
gph[j] = (gph[k] + gph[k][j]);
}
max = 0;
for( i = 0;i < towns;i ++ )
for( j = 0;j < towns;j ++ )
if( gph[j] == INF )
return -1;
else if( gph[j] > max )
max = gph[j];
return max;

}

Posted: Mon Feb 21, 2005 12:18 am
by misof
the order of the cycles in your implementation of floyd-warshall is wrong, k must be incremented in the outermost cycle
of course, the easiest (and recommended) way to remember this is to understand why the algorithm works and what exactly it computes...

Posted: Mon Feb 21, 2005 5:07 am
by murtaza
Changed that ..... still WA ... can anyone give me some i/o's to check ???
thanx

10803 WA help please

Posted: Wed May 18, 2005 8:16 am
by wos
I spent a few days trying to fix this, no luck, i read the other subject on this problem again no luck :D. So if anyone can give me some test data, i would be very thankful, or point out something wrong in my code ?

Code: Select all

#include <cstdio>
#include <climits>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

double sqr(int n)
{
  return double(n*n);
}

int sqri(int n)
{
  return n*n;
}

double dist(pair<int, int> a, pair<int, int> b)
{  
  if (sqri(a.first - b.first) + sqri(a.second - b.second) <= 100)
    return sqrt(sqr(a.first - b.first) + sqr(a.second - b.second));    
  else
    return INT_MAX;
}

int main()
{
  int cases;
  double graph[500][500];
  scanf("%i", &cases);
  vector<pair<int, int> > towns;
  for (int c = 1; c <= cases; c++)
  {    
    printf("Case #%i:\n", c);
    towns.clear();
    int n;
    scanf("%i", &n);    
    for (int i = 0; i < n; i++)    
      for (int j = 0; j < n; j++)
        graph[i][j] = INT_MAX;
    for (int i = 0; i < n; i++)
    {
      int x, y;
      scanf("%i %i", &x, &y);
      towns.push_back(pair<int, int>(x, y));      
    }
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (i != j)
          graph[j][i] = graph[i][j] = dist(towns[i], towns[j]);     
    /*
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
        printf("%15.2lf", graph[i][j]);
      printf("\n");
    }
    */
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
        {
          double tmp = graph[j][i] + graph[i][k];
          if (graph[j][k] > tmp)
            graph[j][k] = tmp;
        }
    double max = 0;
    bool found = false;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (!(abs(graph[i][j] - INT_MAX) < 1e-7) && max < graph[i][j])
        {
          max = graph[i][j];    
          found = true;
        }
    if (!found)
      printf("Send Kurdy\n");
    else
      printf("%.4lf\n", max);
    printf("\n");    
  }
  return 0;
}

Posted: Fri May 20, 2005 3:57 am
by Abednego
Your "infinity" value (INT_MAX) is too big. :-) What happens when inside the Floyd-Warshall, you add INT_MAX and, say, 5?

And also, I don't think your code would ever print "Send Kurdy" because the diagonal entries in the graph are 0.

igor

Posted: Fri May 20, 2005 5:35 am
by mf
Abednego wrote:Your "infinity" value (INT_MAX) is too big. :-) What happens when inside the Floyd-Warshall, you add INT_MAX and, say, 5?
The code assigns INT_MAX to a `double,' so there won't be any overflows.

A test case:

Code: Select all

1

2
0 0
10 0
The correct output is obviously

Code: Select all

Case #1:
10.0000

Posted: Tue May 24, 2005 8:17 am
by wos
Ok i found one problem i was setting the diagonal values to INT_MAX to avoid getting 0 as a result however that was wrong, because FW then fails. I fixed that and the test case gived by mf now works. Also just to be safe i added a check in FW if a value of any of the nodes it's going through is INT_MAX then i skip that step. But still I get WA.