523 - Minimum Transport Cost

All about problems in Volume 5. 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
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sat Oct 18, 2003 5:04 pm

Multiple Input:
http://online-judge.uva.es/problemset/minput.html

Special Correction:
This just means there is possibly more than one correct answer to a given problem. In this case, since it doesn't ask for lexicographically first path, any path of minimal cost will suffice.

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
Location: BANGLADESH

523 WHY RUN TIME ERROR ??

Post by prince56k » Fri Dec 12, 2003 10:56 pm

The code works well in my pc but get runtime error whenever i submit it.
when i remove my dfs() function and submit then RTE becomes W/A.
Is There anybody to help me!!


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cost[100][100],tax[100],path[100][100];
int n,s,d,max=10000;
void getpath(int r,int c)
{
int k;
k=path[r][c];
if(k!=-1)
{
getpath(r,k);
getpath(k,c);
printf("%d-->",k);
}
}
void main(void)
{
char ch;
int i,j,k;
// freopen("523.in","r",stdin);
while(3)
{
scanf("%d%c",&cost[1][++n],&ch);
if(ch=='\n')
break;
}
for(i=2;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[j]);
for(i=1;i<=n;i++)
scanf("%d",&tax);
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
if(cost[j] == -1)
cost[j] = 10000;
path[j]=-1;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if((cost[k]+cost[k][j]+tax[k])<cost[j])
{
cost[j]=cost[k]+cost[k][j]+tax[k];
path[j]=k;
}
while(scanf("%d%d",&s,&d)==2)
{
printf("From %d to %d :\n",s,d);
printf("Path: %d-->",s);
getpath(s,d);
printf("%d\n",d);
printf("Total cost : %d\n\n",cost[s][d]);
}
}

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Dec 22, 2003 12:33 pm

This problem has a green tick associated with it.
Which means it has both multiple input format and correction program.

Nevertheless your code is very similar to mine and I got AC.
So , according to logic, your program should get AC.

If you are a newcomer check for multiple input format.
http://acm.uva.es/problemset/minput.html

Hope it helps. :wink:

Tahseen Mohammad
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

Post by Tahseen Mohammad » Tue Dec 23, 2003 12:32 pm

You have to check the multiple input first.

Then there are some other problem with your floyd-warshalls
path printing portion. I'm not sure if your algo is valid too. But I
don't do it like you do.

Change the following code

Code: Select all

 path[i][j] = k 
to this

Code: Select all

 path[i][j] = path[k][j] 
And my getpath exactly follows that of Coreman's book. So there
is only one recursive call whether you have two.

So look at Coreman. If you have problem understanding that then
please post that and I'll try explaining that.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

523 can someone please look at my code?

Post by little joey » Mon Jan 19, 2004 9:08 pm

Got 10+ WAs using Floyd in a Pascal program about a year ago. Now getting 10+ WAs using Dijkstra and programming in C. Getting kind of desparate. Followed all the suggestions on the board re this problem (I think), but still not dealing correctly with the Judge's f****d up input...

[c]
/* CODE REMOVED; FINALY GOT AC */
[/c]

Added after editing:
Was so focussed on the i/o part, that I didn't notice an error in my dijkstra :oops:
This must be the worst way to set a problem...
Last edited by little joey on Sun Feb 22, 2004 1:11 am, edited 1 time in total.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Jan 20, 2004 12:15 am

Well, I can't tell you what's wrong, but a much simpler way of doing the second part of the input is simply:
[c]char line[1000];
while (getchar() != '\n'); // Eat the end of the previous line.
while (fgets(line, 1000, stdin) && sscanf(line, "%d%d", &from, &to) == 2) {
//handle test case
}
[/c] (i.e. "read lines until we encounter one which doesn't begin with two integers")

Perhaps that would eliminate one possible source of error.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Jan 20, 2004 2:42 am

Thanks for your attention Per. I made the change you suggested. The code looks a lot sleeker now, but still WA...

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
Location: BANGLADESH

Post by prince56k » Fri Jan 23, 2004 10:13 pm

after getting suggestion about multiple input i solved few others but still can't get AC in 523 :( is there still any thing wrong in multiple input handling as we as my get path() function ???

Code: Select all

[c]

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cost[101][101],tax[101],path[101][101];
int n,s,d,max=10000;
void init();
void getpath(int r,int c)
{
	int k;
	k=path[r][c];
	if(k!=-1)
	{
		getpath(r,k);
		getpath(k,c);
		printf("%d-->",k);
	}
}
void main(void)
{
		char ch,str[15],temp[10];
		int i,j,k,total,l,len;
		scanf("%d",&total);
		for(l=0;l<total;l++)
		{
			n=0;
			while(3)
			{
				scanf("%d%c",&cost[1][++n],&ch);
					if(ch=='\n')
						break;
			}
			for(i=2;i<=n;i++)
				for(j=1;j<=n;j++)
					scanf("%d",&cost[i][j]);
			for(i=1;i<=n;i++)
				scanf("%d",&tax[i]);
			for(i=1; i<=n; i++)
				for(j=1; j<=n; j++)
				{
					if(cost[i][j] == -1)
						 cost[i][j] = 10000;
					path[i][j]=-1;
				}
			for(k=1;k<=n;k++)
				for(i=1;i<=n;i++)
					for(j=1;j<=n;j++)
						if((cost[i][k]+cost[k][j]+tax[k])<cost[i][j])
						{
							cost[i][j]=cost[i][k]+cost[k][j]+tax[k];
							path[i][j]=k;
						}
			getchar();
			while(1)
			{
				gets(str);
				len=strlen(str);
				if(len==0)	break;
				s=atoi(str);
				for(i=1;i<len;i++)
					if(str[i]==' ') break;
				for(j=i,k=0;j<len;j++)
					temp[k++]=str[j];
				d=atoi(temp);
				printf("From %d to %d :\n",s,d);
				printf("Path: %d-->",s);
				getpath(s,d);
				printf("%d\n",d);
				printf("Total cost : %d\n\n",cost[s][d]);
				for(i=0;i<k;i++)
					temp[k]='\0';
				for(i=0;i<len;i++)
					str[i]='\0';
			}
			init();
		}
}
void init()
{
	int i,j;
	for(i=0;i<=100;i++)
	{
		for(j=0;j<=100;j++)
			cost[i][j]=0;
		tax[i]=0;	
	}
}

[/c]

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Feb 20, 2004 12:46 pm

It's been a month since I published my code. 10 people got AC in that time, but nobody wants to help me?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Feb 20, 2004 1:43 pm

I think, that matrices aren't in N rows with N elements each.
Try to read N*N values for matrix of size N.
I simple use scanf() to read N*N numbers - only first line I parse to find N.
AFter that I use Floyd algorithm.

EDITED:
Sorry I miss something in your code ...

Best regrads
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Hi:WA and WA and WA...

Post by sumankar » Fri Feb 20, 2004 2:51 pm

Code: Select all

[c]
#include<stdio.h>

#define DIM		8192
#define NIL		-1
#define INFINITY	2000000000
#define MIN(x, y)	((x)>(y)?(y):(x))

int FWAlgo();
void printpath(int i, int j);
void init();
void read();
long int D[DIM][DIM];
long int Tax[DIM];
int Pred[DIM][DIM];
int nvertices;
char buf[1024];

int FWAlgo()
{
	int k, i, j, p;

	for( k = 0; k < nvertices; k++ )
	{
		for( i = 0; i < nvertices; i++ )
		{
			for( j = 0; j < nvertices; j++ )
			{
				if( i != j ) 
				{
					p = D[i][k] + D[k][j] + Tax[k];
					if( p>=D[i][j] )							 
					{
						Pred[i][j] = Pred[i][j];
					}
					else 
					{
						Pred[i][j] = Pred[k][j];
					}
					D[i][j] = MIN(D[i][j], p);
				}
			}
		}
	}
}

void printpath(int i, int j)
{
	if( i == j)
	{
		printf("%d", i+1);
	}
	else if( Pred[i][j] == NIL )
	{
		printf("No path from %d to %d exists.\n", i+1, j+1);
	}
	else 
	{
		printpath(i, Pred[i][j]);
		printf("-->%d", j+1);
	}
}

void read()
{
	int i, len, k, j, c;
	long wt;
	char text[32];

	nvertices = 0;
	if( fgets(buf, 1024, stdin) )
	{
		len = strlen(buf);
		for( i = 0; i < len; )
		{
			k = 0;
			if( buf[i] == '-' || isdigit(buf[i]) )
			{
				do {
					text[k++] = buf[i++];
				}while( isdigit(buf[i]) );
				text[k] = '\0';
				wt = atol(text);
				D[0][nvertices++] = wt<0?INFINITY:wt;
			}
			else i++;
		}
	}
	else exit(0);

	for( i = 1; i < nvertices; i++ )
	{
		for( j = 0; j < nvertices; j++ )
		{
			scanf("%ld", &wt);
			D[i][j] = wt<0?INFINITY:wt;
			Pred[i][j] = i;
		}
	}
	for( i = 0; i < nvertices; i++ )
	{
		scanf("%ld", &Tax[i]);
	}
}

void init()
{
	int i, j;

	for( i = 0; i < DIM; i++ )
	{
		for( j = 0; j < DIM; j++ )
		{
			if( i == j )
			{
				D[i][j] = 0;
			}
			else 
			{
				D[i][j] = INFINITY;
			}
			Pred[i][j] = NIL;
		}
	}
}

int main()
{
	int a, b;
	int ncase;

	scanf("%d", &ncase);
	getchar();
	getchar();
	while( ncase-- )
	{
		read();
		FWAlgo();
		while( getchar() != '\n' )
			;
		while( fgets(buf, 1024, stdin) && sscanf(buf, "%d %d", &a, &b) == 2 )
		{
			printf("From %d to %d :\n", a, b);
			printf("Path: ");
			printpath(a-1, b-1);
			printf("\nTotal cost : %ld\n\n", D[a-1][b-1]);
		}
	}
	return 0;
}
[/c]
Can someone tell me where I am going wrong?
I have lost a lot sleep because of this problem.
(specially: Dominik)
Thank You,
Suman.

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
Location: BANGLADESH

Post by prince56k » Sat Feb 21, 2004 9:32 pm

to sumankar,

u said u r giving WA. but first i got compile error.. then fixed it and found that "Memory Limit Exceed" :o

did u post the desire code u wanted post ?

fpmc
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm

Post by fpmc » Wed Jul 14, 2004 2:28 pm

Hi,

getpath function should be

Code: Select all

void getpath(int r,int c)
{
   int k;
   k=path[r][c];
   if(k!=-1)
   {
      getpath(r,k);
      printf("%d-->",k);
      getpath(k,c);
   }
}
The print goes between the two recursive calls, as 'k' is the itermediate node between 'r' and 'c'.

Frank

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Fri May 06, 2005 12:54 am

ye, 1024 aint enough there, costed me 2 submissions to find out, :lol:

use 1500 for maxn

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

523 - from RTE to WA

Post by WR » Tue May 31, 2005 12:51 pm

Well, I'm not too sure whether to post this question here or under the Programming Languages C thread but here it is anyway:

My program 523 received an Runtime Error (invalid memory reference).

Consequently I inserted too assert-calls to check whether the buffer was big enough and the maximum number of cities was within limits (1500, see yiuyuho's post). Same result.

Then I put in two assert calls to check whether the numbers that represent the cities between which the cargo has to be transported were within limits and this to my very surprise lead to a WRONG ANSWER.

As far as I know the failure of an assertion should trigger a SIGABRT message which leads to a RTE.

So, the C part of my question is: Why does the failure of an assertion lead to a WA?

Now the problem related question is: what should I print in the case that
a query is out of range?

Post Reply

Return to “Volume 5 (500-599)”