11047 - The Scrooge Co Problem

[Jan]

I have some questions about this problem. I have got a lot of Wa's.

1. What if there are multiple paths with min cost?
2. If the source and the destination are the same location and the cost is zero then what should be the output?
3. The problem states -

The next P lines contain the minimum cost to go from one location to another one

The first sample case contains that it is too expensive to go from 1 to 4. But the sample output says that there is a route, for which the cost is less than the input given.
So, how can the given input be the 'minimum cost'?

Weird description? Or I m missing something?

Thanks in advance.

[helloneo]

I have some questions about this problem. I have got a lot of Wa's.

1. What if there are multiple paths with min cost?
2. If the source and the destination are the same location and the cost is zero then what should be the output?
3. The problem states -

The next P lines contain the minimum cost to go from one location to another one

The first sample case contains that it is too expensive to go from 1 to 4. But the sample output says that there is a route, for which the cost is less than the input given.
So, how can the given input be the 'minimum cost'?

Weird description? Or I m missing something?

Thanks in advance.

I think the statement means that 'minimum cost' is the minimum cost among the costs of directly connected roads from a city to another ..
So you can simply ignore the word 'minimum' to solve the problem ..

And I didn't consider the case 1, 2

[ayon]

to jan:
the input is just adjacent matrix. -1 means there is no edge between the two nodes, but there might be some path consisiting two or more edges between the two nodes. i just run simple FW(AC), so if there are multiple paths with min cost anyone can be taken. but i wonder this problem is not yellow marked, might be there is no test case with multiple paths with minimum costs. if source and destination is same you have to printf("Path:%s %s\n", source, dest) i tested this. printing only source or destination will give WA.
"Path:<orig name> <locations separated by a blank> <dest name>"
<locations separated by a blank> is optional, but <orig name> and <dest name> must be present.
hope it make 991 ac

[arsalan_mousavian]

accepted

[Jan]

Thanks helloneo. And special thanks to ayon. I got it accepted and made it to 991 as you wished .

Sometimes we have to ignore a lot of parts from the description.

To arsalan_mousavian,
Try the following test case

Input:

Code: Select all

1
3
Murcia	Alicante	Albacete
-1	3	-1
10	0	4
-1	-1	0
1
Jan Murcia Murcia

Output:

Code: Select all

Mr Jan to go from Murcia to Murcia, you will receive 13 euros
Path:Murcia Alicante Murcia

Hope it helps.

[nymo]

Hi, I am getting WA, can you post some io? ... and is the above io posted by Jan okay, it seems diagonal (i == i) should contain 0[ here, matrix[0][0] contains -1].

[EDIT] Thanks lord_burgos, your i/o helps me to find my error, it has been in the function to print path.

[Jan]

I have tested the input. And I m sure that there are test cases where a is not equal to zero.

You can try it by assert() function.

If you are still getting WA then try reading the post given by ayon.

[lord_burgos]

Input

Code: Select all

2
5
Puebla Mexico Queretaro Durango San_Pedro
2 3 0 1 1
3 0 2 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0
2
Nalley Puebla Puebla
Xuxa Mexico Mexico
3
hola como estas
2 3 0
3 0 2
0 1 0
2
Pedro hola como
Juan como como

Output (Solution AC):

Code: Select all

Mr Nalley to go from Puebla to Puebla, you will receive 0 euros
Path:Puebla Queretaro Durango Puebla
Mr Xuxa to go from Mexico to Mexico, you will receive 0 euros
Path:Mexico Mexico
Mr Pedro to go from hola to como, you will receive 1 euros
Path:hola estas como
Mr Juan to go from como to como, you will receive 0 euros
Path:como como

[lukasP]

Hello,
I am getting WA. My program works good for input posted here. Did you assume that the names of cities don't contain spaces?

[nymo]

Names of cities don't contain spaces.

[C]

My code also passes all i/os here,but i still got WA. Could anyone give some more i/os?

It is a simple shortest-path problem, right ??

[arsalan_mousavian]

My code also passes all i/os here,but i still got WA. Could anyone give some more i/os?

It is a simple shortest-path problem, right ??

yes , but maybe you do some thing wrong in printing the path , or you assign too high value when cost of 2 vertex is -1 that cause integer overflow
Hope it Helps
Arsalan

[C]

or you assign too high value

Thanks Arsalan, but I didn't assign a big value instead of -1, but judge each time if the distance is -1 or not.

but maybe you do some thing wrong in printing the path

I saved the "parent vertex" of each vertex, and then my print algo seems like:

Code: Select all

print(startVertex);
k= endVertex;
while(k.parent!=startVertex)
{
        k= k.parent;
        stack.push(k);
}
while(!empty(stack))
{
       print(s.pop());
}
print(endVertex);

Actually I only used a array to work as a stack.

Any other advices ?? Thanks in advance!!!

[arsalan_mousavian]

add small part to the FW algorithm

Code: Select all

if ( map [i][j] > ( map [i][k] + map [k][j] ) )
				  {
					  map [i][j] = map [i][k] + map [k][j] ;
					  prev[i][j] = k ;
				  }

and you can simply print it recursively
Have Fun !!

[nymo]

Let, d[SIZE][SIZE] and parent[SIZE][SIZE] are respectively the matrix for distance and parent.

Code: Select all

INITIALIZE PORTION:
================
for parent, I use something like this,

void initParent(int noCity)
{
	int i, j;
	
	for (i=0; i<noCity; i++)
	{
		for (j=0; j<noCity; j++)
		{
			if (i == j || d[i][j] == INFINITY) 
				parent[i][j] = NIL;

			else if (i != j && d[i][j] < INFINITY)
				parent[i][j] = i;
		}
	}
}

Inside FW
=======
my code fragment goes something like this...

	if (d[i][j] > d[i][k] + d[k][j])
	{
	    d[i][j] = d[i][k] + d[k][j];
	    parent[i][j] = parent[k][j];
	}

May be I am wrong, but I don't think prev[i][j] = k demonstrated by arsalan_mousavian would produce correct result all the time. Shouldn't it be prev[i][j] = prev[k][j]?
[EDIT] May be we initialize our parent matrix in different ways, It was unwise on my side to say that your fragment may be wrong without considering init portion... sorry. :oops: , don't mind :D 

A simple recursive function then does the trick of printing path:)