## 11015 - 05-2 Rendezvous

Moderator: Board moderators

WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:
By the way, I set all dis[j] to DIS_MAX before reading.
Should I set them to 0 instead?

rudy yulianto
New poster
Posts: 4
Joined: Sun Sep 09, 2007 1:42 pm
Location: Indonesia
Contact:

### please give me some case of input n output

it's my code..
i don't know why WA...

Code: Select all

#include<stdio.h>

int DP[50][50];

int min(int a,int b)
{
if(a<b)
return a;
else
return b;
}

int main()
{
int n,m;
char nama[50][50];
int row,coloumn,cost;
int array[50][50];
int i,j,k;
int temp[500],MIN,index,pendek[500],flag=1;
while(scanf("%d %d",&n,&m)==2)
{
if(n==0||m==0)
break;

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{

if(i==j)
DP[i][j]=array[i][j]=0;

else
DP[i][j]=array[i][j]=999;
}

for(i =1;i<=n;i++)
scanf("%s",nama[i]);

for(i=1;i<=m;i++)
{
scanf("%d %d %d",&row,&coloumn,&cost);
array[row][coloumn]=array[coloumn][row]=cost;
}

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
DP[i][j]=array[i][j];

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
if(i!=j)
temp[k]= min(array[i][j],array[i][k]+array[k][j]);
}

MIN = temp[1];

for(k=2;k<=m;k++)
if(temp[k]<MIN)
MIN = temp[k];

if(i!=j)
DP[i][j]=MIN;
}
}

index=0;
MIN=0;

for(j=1;j<=n;j++)
{
pendek[j]=0;
for(i=1;i<=n;i++)
{
pendek[j]+=DP[i][j];
}

if(j==1)
{
MIN = pendek[1];
index = 1;
}
if(pendek[j]<MIN)
{
MIN=pendek[j];
index=j;
}
}
printf("Case #%d : %s\n",flag,nama[index]);

flag++;
}
return 0;
}

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:
ordering of the FW loop should e for(k) for(i) for(j)
Shihab
CSE,BUET

rudy yulianto
New poster
Posts: 4
Joined: Sun Sep 09, 2007 1:42 pm
Location: Indonesia
Contact:

### wa

my code still wa until now..plz give me some input n output..thx

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
Why do you think that 999 is large enough for infinity?

S.M.ferdous
New poster
Posts: 13
Joined: Fri Nov 03, 2006 2:53 pm
Contact:
just to tell that this program does not have any case regarding multiple edge and M can be zero although program statement does not support this.

qwerty
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

### Re:

Ac
Last edited by qwerty on Sat Oct 31, 2009 2:50 pm, edited 1 time in total.

qwerty
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

### Re: 11015 - 05-2 Rendezvous

someone give me some I/o
Ac
Last edited by qwerty on Sat Oct 31, 2009 2:51 pm, edited 1 time in total.

nayimsust
New poster
Posts: 9
Joined: Wed Aug 27, 2008 6:50 pm

### Re: 11015 - 05-2 Rendezvous

i got wa many times pls help anybody

Code: Select all

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

#define min(a,b)(a<b?a:b)
#define max(a,b)(a>b?a:b)
#define inf 99999999

char name[1001][1001];
long d[1000][1000],t=0,c,c1,c2,s,q,cost,k,i,j,flag[1001],fat,place;

int main()
{
while( scanf("%ld",&c) == 1 && c )
{
scanf("%ld",&s);
for(i=0;i<=c;++i)
for(j=0;j<=c;++j)
{
d[i][i] = d[j][j]=0;
d[i][j]=inf;
flag[i]=0;
}

for(i=1;i<=c;++i)
scanf("%s",name[i]);

for(i=1;i<=s;++i)
{
scanf("%ld %ld %ld",&c1,&c2,&cost);
if(d[c1][c2]>cost)
{
d[c1][c2]=cost;
d[c2][c1]=cost;
flag[c1] = flag[c2] = 1;
}
}

for(k=1;k<=c;++k)
for(i=1;i<=c;++i)
for(j=1;j<=c;++j)
d[i][j]=min( d[i][j] , ( d[i][k] + d[k][j] ) );
fat=inf;
for(i=1;i<=c;++i)
{
cost=0;
if(flag[i]==1)
{
for(j=1;j<=c;++j)
if(flag[j]==1)
cost+=d[i][j];
if(fat>cost)
{
place=i;
fat=cost;
}
}
}
printf("Case #%ld : %s\n",++t,name[place]);
}
return 0;
}

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Contact:

### Re: 11015 - 05-2 Rendezvous

@nayimsust remove flagging. and change the initialization to this

Code: Select all

for(i=0;i<=c;++i)
{
for(j=0;j<=c;++j)
d[i][j]=inf;
d[i][i]=0;
}
Heal The World

shatil_cse
New poster
Posts: 11
Joined: Thu Apr 05, 2012 8:33 pm

### Re: 11015 - 05-2 Rendezvous

got AC......
Last edited by shatil_cse on Sat Apr 07, 2012 6:43 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11015 - 05-2 Rendezvous

Floyd–Warshall should use n instead of m.
Check input and AC output for thousands of problems on uDebug!

shatil_cse
New poster
Posts: 11
Joined: Thu Apr 05, 2012 8:33 pm

### Re: 11015 - 05-2 Rendezvous

brianfry713 wrote:Floyd–Warshall should use n instead of m.
I have got AC.
thanks a lot for ur kind reply

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 11015 - 05-2 Rendezvous

why WA I am going to mad

Code: Select all

[color=#40FF00]#include<stdio.h>
int Min(int a, int b)
{
if(a>b) return b;
else return a;
}

int main()
{
int I,K,L,M,N,W,Case=0;
char Name[30][30];
long Z,X;
while(scanf("%d %d",&N,&M)==2&&N>0)
{
int Mat[50][50][50]={0,0};
Z=10000000;
++Case;
scanf("\n");
for(I=1;I<=N;I++)
gets(Name[I]);
for(I=1;I<=M;I++)
{
scanf(" %d %d %d",&K,&L,&W);
Mat[0][K][L]=W;
Mat[0][L][K]=W;
}

for(I=1;I<=N;I++)
for(K=1;K<=N;K++)
if(Mat[0][I][K]==0) Mat[0][I][K]=10000;

for(K=1;K<=N;K++)
for(I=1;I<=N;I++)
for(L=1;L<=N;L++)
Mat[K][I][L]=Min(Mat[K-1][I][L],(Mat[K-1][I][K]+Mat[K-1][K][L]));

for(I=1;I<=N;I++)
{
X=0;
for(L=1;L<=N;L++)
if(Mat[N][L][I]<10000)
X+=Mat[N][L][I];
if(Z>X) { Z=X; W=I;}
}

printf("Case #%d : %s\n",Case,Name[W]);
}
return 0;
}

[/color]
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11015 - 05-2 Rendezvous

Why is your matrix 3 dimensional?
Check input and AC output for thousands of problems on uDebug!