Page 3 of 3
Posted: Tue May 31, 2005 1:29 pm
by mf
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.
Posted: Wed Jun 01, 2005 7:41 am
by WR
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.
Posted: Wed Jun 01, 2005 11:57 am
by sumankar
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.
Posted: Wed Jun 01, 2005 12:09 pm
by sumankar
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.
Posted: Sun Jun 12, 2005 6:47 am
by yiuyuho
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.
523 WA - need help/test cases
Posted: Mon Aug 21, 2006 3:45 pm
by kamjagin
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[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
Posted: Tue Oct 24, 2006 11:43 pm
by septic
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.. =/
Posted: Sun Jan 21, 2007 9:31 pm
by daveon
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.
Posted: Thu May 03, 2007 3:11 am
by mukeshtiwari
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[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();
}
}
}
Posted: Sun Feb 10, 2008 1:10 pm
by Robert Gerbicz
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).
523-presentation error
Posted: Wed Feb 18, 2015 1:12 pm
by eeriee
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!!!!!!
Re: 523 - Minimum Transport Cost
Posted: Wed Feb 18, 2015 9:29 pm
by brianfry713
Next time post in the existing thread.
Print a blank line between datasets.
Re: 523 - Minimum Transport Cost
Posted: Thu Feb 19, 2015 4:11 am
by eeriee
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
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
But they are all wrong. I have no idea...
Re: 523 - Minimum Transport Cost
Posted: Thu Feb 19, 2015 10:17 pm
by brianfry713
Re: 523 - Minimum Transport Cost
Posted: Mon Jun 15, 2015 7:41 am
by coder21
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;
}