Page 1 of 2
10048 - Audiophobia
Posted: Thu Apr 17, 2003 3:24 am
by deddy one
Hi I just learn a little bit called floyd warshall and try
to solve 10048, but no luck there, it always WA.
I'll patch the code here, could someone tell me
what went wrong, is my floyd warshall understanding
is wrong or what
thx
[c
cut off because it's just a simple mistake
[/c]
Posted: Thu Apr 17, 2003 10:24 am
by turuthok
Deddy, ... I haven't solved this problem yet, but I noticed that you will get a WA when there is an input with 0 dB. For some reason, you replaced it with 9999 ... Why don't you fill out with 9999 first and then read the input.
Good luck,
-turuthok-
Posted: Thu Apr 17, 2003 5:12 pm
by deddy one
ow, I replaced it with 9999 , so that I will
know when there is no path.
I've tried to fill out 9999 first
but still no luck either.
anyway thx very much for
pointing that I'll get WA for
0 decibels.
Any suggestion what I should do ?
Posted: Thu Apr 17, 2003 6:59 pm
by turuthok
Deddy, perhaps it's the following ...
[c]printf ("Case #%d:\n",++set);[/c]
The output doesn't have ':' there ...
-turuthok-
Posted: Thu Apr 17, 2003 7:35 pm
by deddy one
HAHHAHAHAHAHA
oh my goodness
you're right
it get AC now ummm PE actually
thx turuthok
HAVE A NICE DAY
10048 WA
Posted: Mon Sep 08, 2003 11:06 am
by zilnus
I don't know why WA. Is any special test case ?
[c]
int min(int a,int b);
int max(int a,int b);
int main()
{
int weight[100][100],d[100][100],hasil[1000];
int C,S,Q,a,b,berat,i,j,k,kasus = 1;
while (scanf("%d %d %d",&C,&S,&Q))
{
if (!C&&!S&&!Q) break;
for (i=0;i<C;i++)
for (j=0;j<C;j++)
weight[j] = IMP;
for (i=0;i<S;i++)
{
scanf("%d %d %d",&a,&b,&berat);
weight[a-1][b-1] = weight[b-1][a-1] = berat;
}
/* Floyd Warshall */
for (i=0;i<C;i++)
for (j=0;j<C;j++)
d[j] = weight[j];
for (i=0;i<C;i++)
d = 0;
for (k=0; k<C; k++)
for (i=0; i<C; i++)
for (j=0; j<C; j++)
d[j] = min(d[j], max(d[k], d[k][j]));
for (i=0;i<Q;i++)
{
scanf("%d %d",&a,&b);
hasil = d[a-1][b-1];
}
if (kasus > 1) printf ("\n");
printf ("Case #%d\n",kasus);
kasus++;
for(i=0;i<Q;i++)
{
if (hasil == IMP) printf ("no path\n");
else printf ("%d\n",hasil[i]);
}
}
return 0;
}
int min(int a,int b)
{
int x;
if (a < b) x = a;
else x = b;
return x;
}
int max(int a,int b)
{
int x;
if (a > b) x = a;
else x = b;
return x;
}[/c]
Thanx.
Re: 10048 WA
Posted: Mon Sep 22, 2003 6:12 pm
by changgica
zilnus wrote:I don't know why WA. Is any special test case ?
int weight[100][100],d[100][100],hasil[1000];
it should be hasil[10000]
ken
10048
Posted: Tue Nov 11, 2003 7:24 pm
by udvat
** I tried to solve it by floyd's(minimax)
algo.but getting WA again n again. wud anybody plz help me to get the bug?
// code removed
Posted: Wed Nov 12, 2003 6:23 am
by titid_gede
try this input :
output should be :
hope this helps,
-titid gede-
got AC
Posted: Wed Nov 12, 2003 2:09 pm
by udvat
thankx titid. you are right. it was the error in my code. i corrected it and got AC.thank u very much
10048 Why Run Time Error (SIGSEGV)
Posted: Wed Oct 06, 2004 12:24 pm
by efr_shovo
Here Is My Code
#include<stdio.h>
int Path[100][100];
int C,S,Q,c1,c2,d,q1,q2;
int Min(int n1,int n2)
{
if(n1<n2)
return n1;
else
return n2;
}
int Max(int n1,int n2)
{
if(n1>n2)
return n1;
else
return n2;
}
void FW()
{
int k,i,j;
for(i=1;i<=C;i++)
Path=0;
for(k=1;k<=C;k++)
for(i=1;i<=C;i++)
for(j=1;j<=C;j++)
Path[j] = Min( Path[j], Max( Path[k], Path[k][j] ) );
}
void main()
{
int i,j,ca=0;
while(1)
{
scanf("%d %d %d",&C,&S,&Q);
if(C<=0||S<=0||Q<=0)
break;
for(i=1;i<=C;i++)
for(j=1;j<=C;j++)
Path[j]=10000;
for(i=1;i<=S;i++)
{
scanf("%d %d %d",&c1,&c2,&d);
Path[c1][c2]=d;
Path[c2][c1]=d;
}
FW(); /* Floyed Warshall Alg Function*/
if(ca>0)
printf("\n");
printf("Case #%d\n",++ca);
for(i=1;i<=Q;i++)
{
scanf("%d %d",&q1,&q2);
if(Path[q1][q2]==10000)
printf("no path\n");
else
printf("%d\n",Path[q1][q2]);
}
}
}
Posted: Thu Oct 07, 2004 2:49 am
by Junayeed
The size of the array is not sufficient. Use 210 instead of 100.
Hope this will work.
Posted: Thu Oct 07, 2004 6:58 am
by efr_shovo
Thanks This Is worked. But Why Array limite 210 instead of 100? Please
Describe me.
Posted: Thu Oct 07, 2004 7:17 am
by jambon_vn
I think you refer to the out size of the array.
int Path[100][100];
You can only use Path[0][0] to Path[99][99].
When C = 100. See the following code (for example)
for(i=1;i<=C;i++) Path=0;
You assign Path[100][100] --> Run Time Error.
You should change to: Path[101][101]. It will be okie, I do not think you have to chane the size of array to 210.
10048 Audiophobia WA
Posted: Sun Mar 13, 2005 5:17 pm
by tRipper
I've been trying to get AC on this one for some while but without succes. I use floyd warshall algorithm to find the optimal way between all pairs of vertices in the graph
Code: Select all
/* program audiophobia */
#include <iostream>
#include <climits>
using namespace std;
int max(int a, int b) {
if (a>b) return a;
else return b;
}
int main() {
int c,s,n,count;
cin >> c >> s >> n;
while (c || s || n) {
int sound[100][100];
int i,j,k,q;
int c1,c2,d;
if (count) cout << endl;
cout << "Case #" << ++count << endl;
//parse
for (i=0; i<c; i++)
for (j=0; j<c; j++)
sound[i][j]=INT_MAX;
for (i=0; i<s; i++) {
cin >> c1 >> c2 >> d;
sound[c1-1][c2-1]=sound[c2-1][c1-1]=d;
}
// floyd-warshall
for (k=0; k<c; k++ )
for (i=0; i<c; i++)
for (j=0; j<c; j++) {
q=max(sound[i][k],sound[k][j]);
if (q<sound[i][j])
sound[i][j]=sound[j][i]=q;
}
//writesol
for (i=0; i<n; i++) {
cin >> c1 >> c2;
if (sound[c1-1][c2-1]<2000000000)
cout << sound[c1-1][c2-1] << endl;
else cout << "no path\n";
}
cin >> c >> s >> n;
}
return 0;
}