Hi all,

I was just wondering, is it possible to write a solution to the

following problem with the following criteria:

1. it must be as efficient as possible at run-time

2. be in O(1)

3. and be memory efficient

The problem is:

Find the total distance between any two cities if:

Given

source city destination city distance

0 1 5

mi.

1 2 2

mi.

2 3 7

mi.

3 4 8

mi.

etc... for N cities.

Example: distance(0, 4) = 5+2+7+8 = 22

The distance function is being called millions and millions of times

and the list of cities and distances do not change after the program

starts.

I initially thought that making an N X N matrix to store all distances

bwteen cities would be a fast way to retrive any distace (the matrix

would be populated as requests for distances are made), i.e. receive

request, if request not in matrix calculate distance from array, store

result in matrix, output result. But the N x N matrix turned out to be

memory expensive.

Ok. so I thought a hash table with a linked list (for collisions) would

solve my memory problem, but I'm not sure whether or not it satisfies

all the requirements for this solution...

What do you guys think?