523 - Minimum Transport Cost
Moderator: Board moderators
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.
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.
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.![:D](./images/smilies/icon_biggrin.gif)
Regards,
Suman.
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.
![:D](./images/smilies/icon_biggrin.gif)
Regards,
Suman.
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.
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.
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)
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[1500];
long path[1500];
long i,t,antal,N=0, notlast=0;
int main(void)
{
scanf("%i", &antal);
scanf("%i",&temp[0]);
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[0][j][0]=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][0]);
}
}
/* 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][0]==-1)
A[l][j][0]=MAX;
else
A[l][j][0]+=tax[l];
}
}
for(long l=0;l<N;l++)
{
A[l][l][0]=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[0]+"\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][0]==MAX) way[i][j][0] = -1;
else way[i][j][0] = 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;
}
answers for test cases
can you provide me with answers for this test case?
or isn't it necessary to sort it lexicografically?
i get WA, and don't realise what i am doing wrong.. =/
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
i get WA, and don't realise what i am doing wrong.. =/
My output:
I don't remember needing to sort anything.
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
-
- 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 .
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[1000][1000],pre[1000][1000];
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[0][k];
if(pathcost[0][k]==-1)
pathcost[0][k]=inf;
k++;
}
}
return(k);
}
int main()
{
int m1,citytax[1000],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();
}
}
}
-
- 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:
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).
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 Dijkstra really works here. Not using tricks it took 0.02 sec. to solve the problem (on the new judge).
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.
Anyone who got AC before? Please help!!!!!!
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.
Anyone who got AC before? Please help!!!!!!
-
- 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.
Print a blank line between datasets.
Check input and AC output for thousands of problems on uDebug!
Re: 523 - Minimum Transport Cost
Sorry I am new here...brianfry713 wrote:Next time post in the existing thread.
Print a blank line between datasets.
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
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
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
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
Last edited by brianfry713 on Thu Feb 19, 2015 10:18 pm, edited 1 time in total.
Reason: Added code blocks
Reason: Added code blocks
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 523 - Minimum Transport Cost
http://www.udebug.com/UVa/523
Post your code.
Post your code.
Check input and AC output for thousands of problems on uDebug!
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
Reason: Added code blocks