Page 3 of 4
Posted: Tue May 24, 2005 12:35 pm
by mf
More test cases:
Output:
Code: Select all
Case #1:
0.0000
Case #2:
Send Kurdy
Maybe there are no test cases like the 1st one above in the judge's input, the problem statement doesn't say that the cities always have unique coordinates.
And by the way, you can use the value 1.0 / 0.0 as +infinity.
Posted: Thu May 26, 2005 8:41 am
by wos
Ok i solved it at last. The problem was i didn't read carefuly enough. I thought that you should output "Send Kurdy" when there are no ways to get from any town to any other, and not when there is only one such way. Thanks for your help.
Posted: Sun Jun 05, 2005 6:46 am
by roticv
I did the following. According to the sample input, it works, but I don't know why I still got a WA.
Code: Select all
#include <stdio.h>
#include <math.h>
int z,n,N,i,j,k;
int x[105], y[105];
double w[105][105],tmp,max;
double sq(int a){
return (double)a*a;
}
int main(){
scanf("%d ",&N);
for (z=0;z<N;z++){
scanf("%d",&n);
for (i=0;i<n;i++){
scanf("%d %d",&x[i],&y[i]);
}
for (i=0;i<n;i++){
for (j=i+1;j<n;j++){
tmp = sq(x[i]-x[j])+sq(y[i]-y[j]);
tmp = sqrt(tmp);
w[i][i] = 0;
if (tmp<=10.0){
w[i][j] = tmp;
w[j][i] = 0;
}else{
w[i][j] = 10000000;
w[j][i] = 10000000;
}
}
}
for (k=0;k<n;k++)
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (w[i][j] > w[i][k] + w[k][j] )
w[i][j] = w[i][k] + w[k][j];
printf("Case #%d:\n",z+1);
max= -1000000;
for (i=0;i<n;i++){
for (j=0;j<n;j++){
if (max < w[i][j])
max = w[i][j];
}
}
if (max >= 10000000)
printf("Send Kurdy\n");
else
printf("%.4lf\n",max);
printf("\n");
}
return 0;
}
Posted: Wed Jun 08, 2005 5:54 am
by Abednego
There is an obvious bug in the way you build the graph. Because of that, your program gives much smaller answers for many of the test cases. Print out the adjacency matrix w before you run Floyd-Warshall and look at it. :-)
Posted: Thu Jun 23, 2005 7:15 pm
by roticv
Thanks alot. It is a very stupid mistake on my part.
10803 - Thunder Mountain
Posted: Fri Oct 13, 2006 8:33 pm
by rhak_so
I get WA , need help .
It is my code
:
Code: Select all
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define MAXVERT 400
#define INFINITO 1000000.0000
#define NULO -1
void inserta_grafo();
void max_dist();
void inicializar();
void floyd();
//void imprimir(double p[][MAXVERT]);
//void imprimir_padre(int p[][MAXVERT]);
//void camino(int origen, int destino);
double grafo[MAXVERT][MAXVERT];
int padre[MAXVERT][MAXVERT];
struct town{
//int ntown;
int x;
int y;
};
town aux[101];
int numvert;
double max;
int cont;
bool flag1;
int main()
{
//freopen("10803.in.txt","r",stdin);
//freopen("10803.out.txt","w",stdout);
int ncasos,x,y;
scanf("%d",&ncasos);
for(int kase=1;kase<=ncasos;kase++)
{
flag1=true;
inicializar();
cont=0;
max=-1.0;
scanf("%d",&numvert);
for(int i=0;i<numvert;i++)
{
scanf("%d %d",&x,&y);
//aux[i].ntown=i;
aux[i].x=x;
aux[i].y=y;
}
inserta_grafo();
floyd();
max_dist();
if(kase==1)
printf("Case #%d:\n",kase);
else
printf("\nCase #%d:\n",kase);
if(flag1==true)
{ //if(max!=-1.0)
max=max*10000.0+0.5;
//int dmax=int(max);
max=double((floor(max))/10000.0);
printf("%.4lf\n",max);
//else
// printf("Send Kurdy\n");
}else
printf("Send Kurdy\n");
}
return 1;
}
void inicializar()
{
for(int i=0;i<MAXVERT;i++)
{
for(int j=0;j<MAXVERT;j++)
{
padre[i][j]=NULO;
if(i==j)
{grafo[i][j]=0.0;
//padre[i][j]=NULO;
}else
{
grafo[i][j]=INFINITO;
//padre[i][j]=j;
}
}
}
}
void inserta_grafo()
{
for(int i=0;i<numvert;i++)
{
for(int j=0;j<numvert;j++)
{
if(i==j)
grafo[i][j]=0;
else{
double d=pow(double(aux[i].x-aux[j].x),2.0)+pow(double(aux[i].y-aux[j].y),2.0);
//printf("%lf %lf\n",ceil(d),floor(10.0));
//if(ceil(d)>floor(10.0))
if(d>100.0)
{
//printf("d: %lf 10.0: %lf\n",d,10.0);
grafo[i][j]=INFINITO;
}else
{
grafo[i][j]=sqrt(d);
}
}
}
}
}
void floyd()
{
for(int k=0;k<numvert;k++)
{
for(int i=0;i<numvert;i++)
{
for(int j=0;j<numvert;j++)
{
double suma=grafo[k][j]+grafo[i][k];
if(grafo[i][j]>suma)
{
grafo[i][j]=suma;
padre[i][j]=k;
}
}
}
}
}
void max_dist()
{int flag=0;
for(int i=0;i<numvert;i++)
{
flag=0;
for(int j=0;j<numvert;j++)
{
if(i!=j)
if(grafo[i][j]<INFINITO)
{
flag=1;
//printf("\nentro y cambio el flag %lf i:%d j:%d\n",grafo[i][j],i,j);
if(grafo[i][j]>max)
{ max=grafo[i][j];
//printf("%d %d max= %lf\n",i,j,max);
}
}
}
if(flag==0)
flag1=false;
}
}
Tired about 10803
Posted: Tue Mar 27, 2007 4:37 pm
by mohsincsedu
I got WA....
Here is my code:
Code: Select all
#include<stdio.h>
#include<math.h>
#define INF 100000
double T[105][105];
double Min(double a, double b, double c)
{
if(a>(b+c+2*sqrt(b*c)))
return (b+c+2*sqrt(b*c));
return a;
}
int Dis(int a,int b, int c, int d)
{
return ((a-c)*(a-c)+(b-d)*(b-d));
}
int main()
{
int n,tst,i,j,k,cas = 1,X[105],Y[105],temp,dis;
double max;
scanf("%d",&tst);
while(tst--)
{
scanf("%d",&n);
for(i = 0;i<n;i++)
for(j = 0;j<n;j++)
T[i][j] = INF;
for(i = 0;i<n;i++)
{
scanf("%d %d",&X[i],&Y[i]);
}
for(i = 0;i<n-1;i++)
{
for(j = i + 1;j<n;j++)
{
dis = Dis(X[i],Y[i],X[j],Y[j]);
if(dis<=100)
{
T[i][j] = T[j][i] = dis;
}
}
}
for(i = 0;i<n;i++)
T[i][i] = 0;
for(k = 0;k<n;k++)
for(i = 0;i<n;i++)
for(j = 0;j<n;j++)
{
T[i][j] = Min(T[i][j],T[i][k],T[k][j]);
}
max = 0;
for(i = 0;i<n;i++)
for(j = 0;j<n;j++)
{
if(max<T[i][j])
max = T[i][j];
}
printf("Case #%d:\n",cas++);
if(max==INF)
printf("Send Kurdy\n\n");
else
printf("%.4lf\n\n",sqrt(max));
}
return 0;
}
What the wrong in my code????
Posted: Wed Mar 28, 2007 4:16 pm
by nymo
To mohsincsedu,
Code: Select all
for(i = 0;i<n;i++)
for(j = 0;j<n;j++)
for(k = 0;k<n;k++)
{
T[i][j] = Min(T[i][j],T[i][k],T[k][j]);
}
is this the way to do FW() ?
Posted: Wed Mar 28, 2007 4:33 pm
by mohsincsedu
What's the problem here???
Any problem within the loops???
To mohsincsedu...
Posted: Wed Mar 28, 2007 4:39 pm
by nymo
Correct way to FW():
Code: Select all
for (k=0; k<n; k++) // According to your code, k should be the outermost
for (i=0; i<n; i++) // index ...
for (j=0; j<n; j++)
{
Process...
}
Posted: Wed Mar 28, 2007 4:42 pm
by mohsincsedu
Still WA.......................
Min() Fuction is defined same way as previous......
bcaz T
[j] is distance^2
So T[j] = Min(T[j],(T[k]+T[k][j])) is not true here.....
Posted: Wed Mar 28, 2007 4:47 pm
by nymo
mohsincsedu, I 've just an overview of your code... Min() should be changed... may be some other flaws... I don't know... your FW() implementation is not okay ....
/* EDIT: I missed the part that you were not finding the actual distance */
Posted: Wed Mar 28, 2007 5:26 pm
by mohsincsedu
I don't understand where is the problem finding distance
T[j] contains sq of distance
so in FW T[j] update by b and c in the following way:
first distance is sqrt(b)
second distance is sqrt(c)
so (sqrt(b)+sqrt(c))^2 = b + c + 2*sqrt(b*c)
what's the Wrong........
Re: 10803 - Thunder Mountain
Posted: Fri Oct 08, 2010 11:24 am
by Shafaet_du
Floyed Warshall can solve the problem easily. Be careful about precision though.Every answer will obey the formula fabs(ans*1e4 - floor(ans*1e4) - 0.5) > 1e-2 is a useless line.
sample i/O:
Code: Select all
3
6
12 10
1 12
4 5
7 9
1 3
10 15
7
15 20
25 30
30 31
26 27
32 19
31 31
21 24
8
15 20
25 30
30 31
26 27
32 19
31 31
21 24
12 10
Code: Select all
Case #1:
15.1935
Case #2:
23.0421
Case #3:
Send Kurdy
good luck!
Re: 10803 - Thunder Mountain
Posted: Fri May 27, 2011 12:15 am
by mostafa_angel
hi...
I got WA for this Problem...
can anybody help...
Code: Select all
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
#define INF 99999.0
typedef struct p{
double x , y;
}point;
point in[110];
double path[110][110];
double dis(point a , point b)
{
return sqrt(((a.x - b.x)*(a.x - b.x)) + ((a.y - b.y)*( a.y - b.y)));
}
int main()
{
double res;
int t , n;
int dcnt;
cin >> t;
int cnt = 1;
bool kur;
while(t--)
{
for(int i = 0 ;i < 110 ; i++)
{
for(int j = 0; j < 110 ; j++)
{
if (i == j)
path[i][j] = 0;
else
path[i][j] = INF;
}
}
kur = false;
res = 0;
cin >> n;
//double a , b;
for(int i =0 ;i < n ; i++)
{
cin >> in[i].x >> in[i].y;
}
bool is;
for(int i = 0 ; i < n ; i++ )
{
is = false;
for(int j = 0 ; j < n ; j++)
{
double tmp = dis(in[i] , in[j]);
if(tmp*tmp <= 100.00 && i != j)
path[i][j] = path[j][i] = tmp , is = true;
}
if(!is)
{
kur = true;
break;
}
}
if(!kur)
{
for(int k = 0 ; k < n ; k++)
{
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
{
path[i][j] = min(path[i][j] , path[i][k] + path[k][j]);
}
}
}
}
/*for(int i = 0 ;i < n ; i++)
{
for(int j = 0; j < n ; j++)
{
printf("i = %d , j = %d , path[i][j] = %lf\n" , i , j , path[i][j]);
}
}*/
for(int i =0 ; i < n ; i++)
res =max(res, *max_element(path[i] , path[i]+n ));
printf("Case #%d:\n",cnt++);
if(!kur)
printf("%0.4lf\n",res);
else
printf("Send Kurdy\n");
//if(t > 0)
printf("\n");
}
return 0;
}