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

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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

523 WHY RUN TIME ERROR ??

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,tax,path;
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[++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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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. Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

523 can someone please look at my code?

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]

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...
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
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;
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
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,tax,path;
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,temp;
int i,j,k,total,l,len;
scanf("%d",&total);
for(l=0;l<total;l++)
{
n=0;
while(3)
{
scanf("%d%c",&cost[++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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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:
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 ...

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

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();
long int D[DIM][DIM];
long int Tax[DIM];
int Pred[DIM][DIM];
int nvertices;
char buf;

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

{
int i, len, k, j, c;
long wt;
char text;

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[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-- )
{
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
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
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 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:
ye, 1024 aint enough there, costed me 2 submissions to find out, use 1500 for maxn

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

523 - from RTE to WA

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?