523 - Minimum Transport Cost

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

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

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

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

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

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

[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.. =/

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

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

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

[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!!!!!!

[brianfry713]

Next time post in the existing thread.
Print a blank line between datasets.

[eeriee]

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

[brianfry713]

http://www.udebug.com/UVa/523
Post your code.

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