11015 - 05-2 Rendezvous

[WingletE]

By the way, I set all dis[j] to DIS_MAX before reading.
Should I set them to 0 instead?

[rudy yulianto]

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

[shihabrc]

ordering of the FW loop should e for(k) for(i) for(j)

[rudy yulianto]

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

[sclo]

Why do you think that 999 is large enough for infinity?

[S.M.ferdous]

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]

Ac

[qwerty]

someone give me some I/o
Ac

[nayimsust]

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]

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

[shatil_cse]

got AC......

[brianfry713]

Floyd–Warshall should use n instead of m.

[shatil_cse]

Floyd–Warshall should use n instead of m.

I have got AC.
thanks a lot for ur kind reply

[mahade hasan]

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]

[brianfry713]

Why is your matrix 3 dimensional?