10048 - Audiophobia

[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]

[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-

[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 ?

[turuthok]

Deddy, perhaps it's the following ...

[c]printf ("Case #%d:\n",++set);[/c]

The output doesn't have ':' there ...

-turuthok-

[deddy one]

HAHHAHAHAHAHA

oh my goodness
you're right

it get AC now ummm PE actually

thx turuthok

HAVE A NICE DAY

[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.

[changgica]

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

[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

[titid_gede]

try this input :

Code: Select all

100 0 1
1 2
0 0 0

output should be :

Code: Select all

Case #1
no path

hope this helps,
-titid gede-

[udvat]

thankx titid. you are right. it was the error in my code. i corrected it and got AC.thank u very much

[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]);
}
}
}

[Junayeed]

The size of the array is not sufficient. Use 210 instead of 100.

Hope this will work.

[efr_shovo]

Thanks This Is worked. But Why Array limite 210 instead of 100? Please
Describe me.

[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.

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