11015 - 05-2 Rendezvous

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Post by WingletE » Tue Aug 28, 2007 4:05 pm

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

Post by rudy yulianto » Sat Dec 01, 2007 5:13 pm

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;
}
i need some sample input n output..please help me...THX
sorry my english is bad

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

Post by shihabrc » Sat Dec 01, 2007 6:23 pm

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

Post by rudy yulianto » Thu Dec 06, 2007 2:49 pm

my code still wa until now..plz give me some input n output..thx
sorry my english is bad

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Dec 07, 2007 3:39 am

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
Location: bangladesh
Contact:

Post by S.M.ferdous » Sun Dec 30, 2007 8:02 pm

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:

Post by qwerty » Sun Oct 25, 2009 1:20 pm

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

Post by qwerty » Wed Oct 28, 2009 6:05 am

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

Post by nayimsust » Wed Oct 28, 2009 7:51 pm

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
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 11015 - 05-2 Rendezvous

Post by calicratis19 » Thu Oct 29, 2009 2:35 pm

@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;
                    }
and please remove your code if accepted.
Heal The World

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

Re: 11015 - 05-2 Rendezvous

Post by shatil_cse » Thu Apr 05, 2012 8:51 pm

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

Post by brianfry713 » Sat Apr 07, 2012 1:10 am

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

Post by shatil_cse » Sat Apr 07, 2012 6:38 pm

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

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 11015 - 05-2 Rendezvous

Post by mahade hasan » Thu May 17, 2012 5:16 pm

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

Post by brianfry713 » Fri May 18, 2012 12:19 am

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

Post Reply

Return to “Volume 110 (11000-11099)”