Page 2 of 4
Posted: Fri Jan 14, 2005 3:04 pm
I got AC.Don't need test data. Eduard.

Posted: Tue Jan 18, 2005 12:42 pm
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
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
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
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
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
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
I got it accepted: it was an stupid error about the output format.

Thanks everybody.

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

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

#define INF 999999999

int grid;
float gph;

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], &grid[j] );
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]-grid[m])*(grid[j]-grid[m])+(grid[j]-grid[m])*(grid[j]-grid[m]);
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
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
Changed that ..... still WA ... can anyone give me some i/o's to check ???
thanx

Posted: Wed May 18, 2005 8:16 am
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;
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
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
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
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.