## 10803 - Thunder Mountain

**Moderator:** Board moderators

I got AC.Don't need test data.

Eduard.

Eduard.

someone who like to solve informatic problems.

http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

- Ndiyaa ndako
- New poster
**Posts:**21**Joined:**Sat Sep 25, 2004 3:35 am**Location:**Oaxaca de Ju-
**Contact:**

### Wrong answer.

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.

I check that but I still get "Wrong Answer". What's wrong?

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];
```

- Ndiyaa ndako
- New poster
**Posts:**21**Joined:**Sat Sep 25, 2004 3:35 am**Location:**Oaxaca de Ju-
**Contact:**

### My method.

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.

I have tried that code with both the cases i==j and i != j.

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];
}
```

Code: Select all

`grafo[k-1][i][j] = grafo[k-1][i][k] + grafo[k-1][k][j]; `

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

- Ndiyaa ndako
- New poster
**Posts:**21**Joined:**Sat Sep 25, 2004 3:35 am**Location:**Oaxaca de Ju-
**Contact:**

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

#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]) )*

gphgph

*[j] = (gph**[k] + gph[k][j]);*

}

max = 0;

for( i = 0;i < towns;i ++ )

for( j = 0;j < towns;j ++ )

if( gph}

max = 0;

for( i = 0;i < towns;i ++ )

for( j = 0;j < towns;j ++ )

if( gph

*[j] == INF )*

return -1;

else if( gphreturn -1;

else if( gph

*[j] > max )*

max = gphmax = gph

*[j];*

return max;

}return max;

}

Putting n programmers on a problem will not result in the time of solving the problem to reduce by n.

### 10803 WA help please

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;
}
```

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

A test case:

Code: Select all

```
1
2
0 0
10 0
```

Code: Select all

```
Case #1:
10.0000
```