## 11047 - The Scrooge Co Problem

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### 11047 - The Scrooge Co Problem

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?

Ami ekhono shopno dekhi...
HomePage

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11047 - The Scrooge Co Problem

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?

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
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
accepted
Last edited by arsalan_mousavian on Sun Jun 04, 2006 8:16 pm, edited 3 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### Please someone post some i...

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.
Last edited by nymo on Mon Jun 05, 2006 1:21 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:
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
New poster
Posts: 3
Joined: Mon Aug 08, 2005 12:44 pm
Location: Pezinok, Slovakia
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
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
Names of cities don't contain spaces.

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm
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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
C wrote: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
In being unlucky I have the record.

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm
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.

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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 !!
In being unlucky I have the record.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### For printing path:)

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:)
``````
Last edited by nymo on Wed Jun 07, 2006 8:58 am, edited 1 time in total.