523 - Minimum Transport Cost

[UFP2161]

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]

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

[sohel]

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.

[Tahseen Mohammad]

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.

[little joey]

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
This must be the worst way to set a problem...

[Per]

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.

[little joey]

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

[prince56k]

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]

[little joey]

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]

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

[sumankar]

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]

to sumankar,

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

did u post the desire code u wanted post ?

[fpmc]

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]

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

use 1500 for maxn

[WR]

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?