10803 - Thunder Mountain

[Eduard]

I got AC.Don't need test data.
Eduard.

[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?

[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 ?

[Larry]

How do you do the Floyd/Warshall? Do you assume f(a,a) is true?

[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.

[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??

[Larry]

Monsoon, you don't need that. A two dimension array is enough.

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

[Ndiyaa ndako]

I got it accepted: it was an stupid error about the output format.

Thanks everybody.

[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;

}

[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...

[murtaza]

Changed that ..... still WA ... can anyone give me some i/o's to check ???
thanx

[wos]

I spent a few days trying to fix this, no luck, i read the other subject on this problem again no luck . 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;
}

[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

[mf]

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

[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.