523 - Minimum Transport Cost
Moderator: Board moderators
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[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]);
}
}
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]);
}
}
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.
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
- Location: Bangladesh
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
to this
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.
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
Code: Select all
path[i][j] = path[k][j]
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.
-
- 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]
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...
[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...
Last edited by little joey on Sun Feb 22, 2004 1:11 am, edited 1 time in total.
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.
[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.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 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]
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
-
- 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 ...
Best regrads
DM
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)
Born from ashes - restarting counter of problems (800+ solved problems)
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();
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]
I have lost a lot sleep because of this problem.
(specially: Dominik)
Thank You,
Suman.
Hi,
getpath function should be
The print goes between the two recursive calls, as 'k' is the itermediate node between 'r' and 'c'.
Frank
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);
}
}
Frank
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?
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?