534

Dominik Michniewski · Post by **Dominik Michniewski** » Wed Sep 25, 2002 8:10 am

Could anyone help me?
I use to solve this problem following algorith:

1. read data
2. build full graph - compute connections to all other stones from any.
3. use BFS to find minimal distance which is necessary to reach every stone from all other.
4. output result

What do I miss?
Could anyone send me some special cases?
Is there a problem with rouding errors ?

Best regards
Dominik

yiuyuho · Post by **yiuyuho** » Tue Apr 08, 2003 6:12 am

BFS to find minimal distance?

I don't understand, may be you implement it differently. But a BFS will reach all vertices and stop, right, which you only compute the distance from one stone to all others, but nothing about inter-connection?

Or Am I misunderstanding?

yiuyuho · Post by **yiuyuho** » Tue Apr 08, 2003 6:16 am

Is there another way of doing this problem by MST, Prims?

turuthok · Post by **turuthok** » Tue Apr 08, 2003 7:34 am

I just got this AC-ed this morning ... I used Floyd-Warshall for this problem ...

-turuthok-

Dominik Michniewski · Post by **Dominik Michniewski** » Tue Apr 08, 2003 7:45 am

I change my implementation to Floyd and got Acc too ....

Thanks all
DM

anupam · Post by **anupam** » Tue Apr 08, 2003 9:10 am

i also used dfs for the first time and got TLE..
then i just changed it to floyd and got ac..
actually the statement of the problem is confusing...
---
anupam

sunkist · Post by **sunkist** » Sun Jun 15, 2003 2:27 am

Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

[c]
#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long min(long a,long b) {
if (a > b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[0],&coord[1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[0] - coord[j][0]);
l = (long) (coord[1] - coord[j][1]);
matrix[j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k))
if (matrix[k] > min(matrix[j],matrix[j][k]))
matrix[k] = min(matrix[j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
[/c]

sunkist · Post by **sunkist** » Sun Jun 15, 2003 2:31 am

Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

[c]
#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long min(long a,long b) {
if (a > b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[0],&coord[1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[0] - coord[j][0]);
l = (long) (coord[1] - coord[j][1]);
matrix[j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k))
if (matrix[k] > min(matrix[j],matrix[j][k]))
matrix[k] = min(matrix[j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
[/c]

sunkist · Post by **sunkist** » Sun Jun 15, 2003 2:41 am

Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

[c]
#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long max(long a,long b) {
if (a < b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[0],&coord[1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[0] - coord[j][0]);
l = (long) (coord[1] - coord[j][1]);
matrix[j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k) && (i != k))
if (matrix[k] > max(matrix[j],matrix[j][k]))
matrix[k] = max(matrix[j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
[/c]

sunkist · Post by **sunkist** » Sun Jun 15, 2003 2:47 am

Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

[c]
#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long max(long a,long b) {
if (a < b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[0],&coord[1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[0] - coord[j][0]);
l = (long) (coord[1] - coord[j][1]);
matrix[j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k) && (i != k))
if (matrix[k] > max(matrix[j],matrix[j][k]))
matrix[k] = max(matrix[j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
[/c]

sunkist · Post by **sunkist** » Sun Jun 15, 2003 2:48 am

Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

Code: Select all

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

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long max(long a,long b) {
   if (a < b) return b;
   else return a;
}

int main () {
   while (1) {
      scanf("%d",&n);
      if (n == 0) return 0;
      memset(matrix,0,sizeof(matrix));
      for (i = 0;i < n;i++) scanf("%d %d",&coord[i][0],&coord[i][1]);
      for (i = 0;i < n;i++) {
         for (j = 0;j < n;j++) {
            if (i != j) {
               k = (long) (coord[i][0] - coord[j][0]);
               l = (long) (coord[i][1] - coord[j][1]);
               matrix[i][j] = k * k + l * l;
            }
         }
      }
      for (i = 0;i < n;i++) {
         for (j = 0;j < n;j++) {
            for (k = 0;k < n;k++) {
               if ((i != j) && (j != k) && (i != k))
                  if (matrix[i][k] > max(matrix[i][j],matrix[j][k]))
                     matrix[i][k] = max(matrix[i][j],matrix[j][k]);
            }
         }
      }
      printf("Scenario #%d\n",count);
      printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
      count++;
   }
}

bigbit · Post by **bigbit** » Fri Jun 27, 2003 3:44 pm

What is output for:

5
1 0
2 0
3 0
4 0
4 1

I need more test cases. Please help!

Eduard · Post by **Eduard** » Wed Apr 07, 2004 9:54 pm

Please help me.Tell me where I'm worong.
I use Floyd Warshal's algoritm.
[pascal] Deleted...[/pascal]

Eduard · Post by **Eduard** » Thu Apr 08, 2004 6:19 pm

I find my bag ... at the beginning matrix must be infinity(like a maxlongint) not 0.

wanderley2k · Post by **wanderley2k** » Wed Sep 01, 2004 12:20 pm

Hi,

I tried to solve the 534 and implemented MST-Kruskal and nothing.

Do Problem want to know the minimax jumpy? Ok?

Have Someone input for test?

My Code:

[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_VERTICES 205
#define MAX_ARESTAS 206*206
#define INFINITO 1000000000000.0

typedef struct {
int x, y;
} Ponto;

typedef struct {
int u, v;
bool usada;
double peso;
} Aresta;

Aresta arestas[MAX_ARESTAS]; // Conjunto de Arestas
int id[MAX_VERTICES]; // id da componente que o vertice esta
int sz[MAX_VERTICES]; // Tamanho da componente
int numArestas; // N

OJ Board

534 - Frogger

534 - Frogger

534-frogger- help!

534: Why wrong? Is MST solution?