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/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650

 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 FloydWarshall
// 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];

 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];
}
I think that your implementation of FloydWarshall algorithm is wrong. Becouse you should create matrix [1..n,1..n,1..n]. And it should looks like this
ofcourse you can reduce the matrix to [1..2,1..n,1..n].
Maybe i'm wrong, i don't why you use closure??
Code: Select all
grafo[k1][i][j] = grafo[k1][i][k] + grafo[k1][k][j];
Maybe i'm wrong, i don't why you use closure??

 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[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;
}
#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;
}
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) < 1e7) && 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 FloydWarshall, 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
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.