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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I don't think yiuyuho is right, my accepted program assumes there's at most 128 cities.
And so your assertions simply didn't fail.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
Thanks for the reply, mf, but I'm afraid that doesn't answer my question(s).

There are two critical parts of my program, that is two parts where an invalid memory reference could occur:

1) reading the input and increasing the city-counter

2) reading the city-numbers between cargo is transported

Just adding two asserts in the 2nd part changed the OJ's answer from runtime error to wrong answer and this is exactly what I do not understand.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
I am getting RTE as well .002/.008/.070 sec with ncities = 256/512/1500 respectively.
1. Suppose there are 10 cities and the query asks you to find a route from 3 to 13 - are you handling that?
2. What are you printing as cost when Cost(u, v) = INF ? I print -1.
3. Are you printing the "Path: " stuff at all when Cost(u, v) = INF ?
4. For cost(u, u) , I print for path: "Path: u\n". Is this okay?

[edit: a few minutes later]
... and now AC.Init routine for the cost matrix was erroneous. Regards,
Suman.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
More news!
Max number of cities is a _LOT_ less than 1500. But not too sure
if 128 is enough as that gave me another RTE Reduced my runtime by about 1/4th.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
WR, as you might already know, in C, Invalid memory reference, or in general access viiolation does not always cause runtime interrupt. What happen is your program will be assigned a block of memory, and if you reference and index that is out of range of ur array, there is 2 cases:

1) The memory you are trying to reference is OUTSIDE of your program block, in that case, you'll recevive a System runtime Error.

2) The memory you are trying to reference is Inside your program block, which means, your are accessing some variable or code segment (that is, of course, not a member of the array) of your program, most likely some other variable, and in this case there wont be a system runtime Error because everything happens within your program.

You might have a v[n] or v[-1] somewhere tat caused it.

As far as limit concern, I use 1500 and get accepted, did not work with the limit specified (may be I did something wrong), there can be lower bounds.

kamjagin
New poster
Posts: 1
Joined: Mon Aug 21, 2006 3:31 pm

523 WA - need help/test cases

Hello.
I've been trying to solve this one for a long time now..
First I started with java(since its my main language), but I couldn't get it to go fast enough. Later I saw that only one person or something like that had solved this one in Java, so i figured that maybe I had a better shot at it in C.

Though I'm not very proficient in C I managed to write some ugly code that solves the test cases.

But I keep getting wrong answer... I've looked at my output- printer and it looks ok. Haven't found any strange stuff with the algoritm either.

Does anyone have an idea?

(Must be compiled as c++ to work)

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

#define MAX 1600001

void floyds(long);
long min(long ett, long tva);
void printO(long ,long,long);
void process();

long *** way, *** A;
long *tax;
long temp;
long path;
long i,t,antal,N=0, notlast=0;

int main(void)
{

scanf("%i", &antal);
scanf("%i",&temp);

for(i=0;i<antal;i++)
{
N=1; // The first zero is already read

char ch;

/* Read in first row so that we can allocate enough memory*/
while(1)
{
scanf("%c",&ch);
if(ch==' ');/*do nothing*/
else if(ch=='\n') break;
else if(ch=='-')
{
int h=0;
t=0;
scanf("%c",&ch);
while(ch!=' ' && ch!='\n')
{

t+=(long)pow(10,h)*(int)(ch-48);
scanf("%c",&ch);
h++;

}
if(h>0)
{
temp[N]=-t;
N++;
}
if(ch=='\n')
break;
}
else
{
int h=0;
t=0;
while(ch!=' ' && ch!='\n')
{
t+=(long)pow(10,h)*(int)(ch-48);
scanf("%c",&ch);
h++;

}
if(h>0)
{
temp[N]=t;
N++;
}
if(ch=='\n')
break;
}
}

A=(long ***)malloc(N*sizeof(long **));
for(long j=0;j<N;j++)
{
A[j]=(long **)malloc(N*sizeof(long *));
for(long k=0;k<N;k++)
A[j][k]=(long *)malloc((N+1)*sizeof(long));
}

way=(long ***)malloc(N*sizeof(long **));
for(long j=0;j<N;j++)
{
way[j]=(long **)malloc(N*sizeof(long *));
for(long k=0;k<N;k++)
way[j][k]=(long *)malloc((N+1)*sizeof(long));
}
tax=(long *)malloc((N+1)*sizeof(long));

for(long j=0;j<N;j++) // First row
{
A[j]=temp[j];
}

for (long k=1;k<N;k++) // Read in everything else
{
for(long j=0;j<N;j++)
{
scanf("%i",&A[k][j]);
}
}

/* Reading in tax */
for(long j=0;j<N;j++)
{
scanf("%i",&tax[j]);
}

for(long l=0;l<N;l++)  //compensate for the tax
{
for(long j=0;j<N;j++)
{
if (A[l][j]==-1)
A[l][j]=MAX;
else
A[l][j]+=tax[l];
}
}
for(long l=0;l<N;l++)
{
A[l][l]=0;
}

floyds(N);
process();

for(long j=0;j<N;j++)
{
for(long k=0;k<N;k++)
free(A[j][k]);
free(A[j]);
}
free(A);
for(long j=0;j<N;j++)
{
for(long k=0;k<N;k++)
free(way[j][k]);
free(way[j]);
}
free(way);
free(tax);
}

}
void process()
{
long f,t,w;
while(1)
{

long g=scanf("%i",&f);
if (f==0 || g!=1)
break;
if(notlast)
printf("\n");
scanf("%i",&t);
printf("From %i to %i : \nPath: ",f,t);
long pa=2;
w=t-1;
if(f!=t && f>0 && t>0 && f<=N && t<=N && -1!=way[f-1][w][N])
{
while(w!=f-1)
{
w=way[f-1][w][N];
path[pa]=w+1;
pa++;
}
path[pa]=(A[f-1][t-1][N]-tax[f-1]);
}
else if( f==t )
{
path[pa]=-1;//g+"\nTotal cost : 0";
}
else
{
path[pa]=-2;//"\nTotal cost : ";
}
printO(pa,f,t);
printf("\n");
notlast=1;

}
}
void printO(long pa, long from,long to)
{
if(from==to)
{
printf("%i\nTotal cost : 0",from);
}
else if(path[pa]==-2)
{
printf("\nTotal cost : ");
}
else
{
printf("%i",path[pa-1]);
for(long i=(pa-2);i>1;i--)
{
printf("-->%i",path[i]);

}
printf("-->%i",to);
printf("\n");
printf("Total cost : %i",path[pa]);
}

}
void floyds(long N)
{

for (long i=0;i<N;i++){
for (long j=0;j<N;j++){
if (i==j || A[i][j]==MAX) way[i][j] = -1;
else way[i][j] = i;
}
}
for (long k=0;k<N;k++)
{
for (long i=0;i<N;i++)
{
for (long j=0;j<N;j++)
{
A[i][j][k+1] = min(A[i][j][k], A[i][k][k]+A[k][j][k]);
if (A[i][j][k]<= A[i][k][k]+A[k][j][k])
way[i][j][k+1] = way[i][j][k];
else way[i][j][k+1] = way[k][j][k];
}
}
}

}

long min(long ett, long tva)
{
if (ett<tva)
return ett;
return tva;
}

septic
New poster
Posts: 1
Joined: Tue Oct 24, 2006 11:29 pm
Contact:

answers for test cases

can you provide me with answers for this test case?

Code: Select all

1

0 1 -1 -1 3
1 0 1 -1 -1
-1 1 0 1 -1
-1 -1 1 0 1
3 -1 -1 1 0
0 1 1 0 1
1 4
4 1
2 2
or isn't it necessary to sort it lexicografically?
i get WA, and don't realise what i am doing wrong.. =/

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
My output:

Code: Select all

From 1 to 4 :
Path: 1-->2-->3-->4
Total cost : 5

From 4 to 1 :
Path: 4-->3-->2-->1
Total cost : 5

From 2 to 2 :
Path: 2
Total cost : 0
I don't remember needing to sort anything.

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india
Getting WA plz help me ..
i use floyd's algorithm to compute all pair shortest path .here is my code.plz check my code output against accepted code .

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define inf 1000000
int pathcost,pre;
int takeinput()
{
int j,k=0,m;
char c;
while(cin.get(c) &&  c!='\n')
{
if((c>='0' && c<='9') || (c=='-'))
{
cin.unget();
cin>>pathcost[k];
if(pathcost[k]==-1)
pathcost[k]=inf;
k++;
}
}
return(k);
}

int main()
{
int m1,citytax,w,i,j,k,t1,t2,t;
char c;

scanf("%d",&m1);
int w1=m1;
getchar();//one for \n and anthor for blank line
getchar();
while(m1--)
{
if(m1!=w1-1)
printf("\n");
w=takeinput();
for( i=1;i<w;i++)
for( j=0;j<w;j++)
{
cin>>pathcost[i][j];
if(pathcost[i][j]==-1)
pathcost[i][j]=inf;
}

for(i=0;i<w;i++)
cin>>citytax[i];

getchar();

for(i=0;i<w;i++)
for(j=0;j<w;j++)
pre[i][j]=i;

for(k=0;k<w;k++)
{
for(i=0;i<w;i++)
{
for(j=0;j<w;j++)
{
if(pathcost[i][j]>pathcost[i][k]+pathcost[k][j]+citytax[k])
{
pathcost[i][j]=pathcost[i][k]+pathcost[k][j]+citytax[k];
pre[i][j]=pre[k][j];
}
}
}
}
int w2=0;
while(cin.get(c) && c!='\n')
{
if(w2!=0)
printf("\n");
w2=1;
cin.unget();
cin>>t1>>t2;
printf("From %d to %d :\n",t1,t2);
printf("Path: ");
i=0;
j=t1-1;
k=t2-1;
t=t2-1;
printf("%d",(j+1));
while(j!=k && i<3)
{
while(j!=pre[j][t])
{
t=pre[j][t];
}
printf("-->%d",(t+1));
j = t;
t = k;
i++;
}
printf("\n");
printf("Total cost : %d\n",pathcost[t1-1][t2-1]);
getchar();
}

}
}

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
My opinion is that the input has correct form (I've read the input in binary form), but the sample output is wrong. The correct output (for sample input) should be from my AC code:

Code: Select all

From 1 to 3 :
Path: 1-->5-->4-->3
Total cost : 21
From 3 to 5 :
Path: 3-->4-->5
Total cost : 16
From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17
And there is only blank lines between datasets.
And Dijkstra really works here. Not using tricks it took 0.02 sec. to solve the problem (on the new judge).

eeriee
New poster
Posts: 2
Joined: Wed Feb 18, 2015 1:06 pm

523-presentation error

I have tried three kinds of output as follows but all show presentation error.

1. only a blank line between each dataset.
2. a blank line between each path of a dataset and additional blank line between dataset.
3. every path of all datasets is seperated by a blank line.

And all of them don't print a blank line at the end of all test cases.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 523 - Minimum Transport Cost

Next time post in the existing thread.
Print a blank line between datasets.
Check input and AC output for thousands of problems on uDebug!

eeriee
New poster
Posts: 2
Joined: Wed Feb 18, 2015 1:06 pm

Re: 523 - Minimum Transport Cost

brianfry713 wrote:Next time post in the existing thread.
Print a blank line between datasets.
Sorry I am new here...

I printed a blank line between datasets.

The input is:

Code: Select all

2

0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
1 1
3 5
2 4

0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
2 5
3 5
1 4
Ane my three-version outputs are:
First:

Code: Select all

From 1 to 1 :
Path: 1
Total cost : 0

From 3 to 5 :
Path: 3-->4-->5
Total cost : 16

From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17

From 2 to 5 :
Path: 2-->1-->5
Total cost : 12

From 3 to 5 :
Path: 3-->4-->5
Total cost : 16

From 1 to 4 :
Path: 1-->5-->4
Total cost : 9
Second:

Code: Select all

From 1 to 1 :
Path: 1
Total cost : 0

From 3 to 5 :
Path: 3-->4-->5
Total cost : 16

From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17

//two blank lines here
From 2 to 5 :
Path: 2-->1-->5
Total cost : 12

From 3 to 5 :
Path: 3-->4-->5
Total cost : 16

From 1 to 4 :
Path: 1-->5-->4
Total cost : 9
Third:

Code: Select all

From 1 to 1 :
Path: 1
Total cost : 0
From 3 to 5 :
Path: 3-->4-->5
Total cost : 16
From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17

From 2 to 5 :
Path: 2-->1-->5
Total cost : 12
From 3 to 5 :
Path: 3-->4-->5
Total cost : 16
From 1 to 4 :
Path: 1-->5-->4
Total cost : 9
But they are all wrong. I have no idea...
Last edited by brianfry713 on Thu Feb 19, 2015 10:18 pm, edited 1 time in total.
Reason: Added code blocks

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 523 - Minimum Transport Cost

Check input and AC output for thousands of problems on uDebug!

coder21
New poster
Posts: 5
Joined: Tue Feb 10, 2015 9:13 am

Re: 523 - Minimum Transport Cost

I am getting RTE...Could anyone please point me where I am getting it wrong. Following is my code:

Code: Select all

#include<iostream>
#include<cstring>
using namespace std;

#define value 999999
#define INF 0x3FFFFFFF
#define SIZE 1001

long input[SIZE][SIZE];
long route[SIZE][SIZE];
long arr[SIZE];

void floydWarshall (int max)
{
int i, j, k;

for (k = 1; k <= max; k++)
{
// Pick all vertices as source one by one
for (i = 1; i <= max; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 1; j <= max; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if(k!=i && k!=j && i!=j)
{
if (input[i][k] + arr[k] + input[k][j] < input[i][j])
{
input[i][j] = input[i][k] + input[k][j] + arr[k];
route[i][j] = route[i][k];
}
}
}
}
}

}

int main()
{
//freopen("input.txt","r",stdin);

int x,y,nodeCount,M,count=1;

cin>>M;
while(M--)
{
if(count>1)
cout<<endl;

char ch=' ';
nodeCount=0;

int i=1,j=1;
while(ch!='\n')
{
cin>>x;
nodeCount++;
if(x==-1)
input[i][j++]=INF;
else
input[i][j++]=x;
cin.get(ch);
}

for(i=2;i<=nodeCount;i++)
{
for(j=1;j<=nodeCount;j++)
{
cin>>x;
if(x==-1)
input[i][j]=INF;
else
input[i][j]=x;
}
}

for(i=1;i<=nodeCount;i++)
cin>>arr[i];

for(i=1;i<=nodeCount;i++)
{
for(j=1;j<=nodeCount;j++)
{
if(i==j)
route[i][j]=0;
else
route[i][j]=j;
}
}

floydWarshall(nodeCount);

int shortestPath[SIZE],index,p, tc=1,charCount=0;
char ch1;
cin.get(ch1);
cin.get(ch1);
if(ch1!='\n')
{
cin.unget();
while(cin>>x>>y)
{
if(tc>1)
cout<<endl;

index=0;
shortestPath[index++] = route[x][y];
p=x;
while(route[p][y]!=y)
{
p = route[p][y];
shortestPath[index++] = route[p][y];
}

cout<<"From "<<x<<" to "<<y<<" :"<<endl;
cout<<"Path: "<<x;
for(i=0;i<index;i++)
cout<<"-->"<<shortestPath[i];
cout<<endl;
cout<<"Total cost : "<<input[x][y]<<endl;

cin.get(ch1);
if(ch1=='\n')charCount++;
else
cin.unget();

cin.get(ch1);
if(ch1=='\n')charCount++;
else
cin.unget();
if(charCount==2)break;
else
charCount=0;
tc++;
}

}
count++;
}
return 0;
}
Last edited by brianfry713 on Fri Jun 19, 2015 6:32 am, edited 1 time in total.
Reason: Added code blocks