Hi everyone
I am trying to solve the following problem
http://www.spoj.com/problems/AMR11F/
The editorials to this problem has a hint that it can be solved by floyd warshall algorithm but it doesnt provide the solution.
My question is how would i represent such kind of a graph using adjacency list or matrix. It would be appreciated if the code will be in c/c++/java/c#/python
Vertices of a graph are:
1) All first floors of all towers
2) All floors connected by some bridge.
So there will be at most N + 2 * M vertices (<=300). For each tower calc distance (in O(1)) between pairs of adjacent vertices.
Run Floyd Warshall algorithm
To answer a query you need to find for each of given froors two nearest vertices and try all possible combinations (at most 4).
Thanx for the help...just one more question i know its a silly one
What is the logic behind 2*M...is it bcoz a bridge connects 2 floors of different towers??
Yes. For example we have N = 100, M = 100, and the edge i connects 5-th floor of tower i with 10-th floor of tower (i+1). there will be 300 vertices. In form (tower, floor): (1, 1) (1, 5) (1, 10) (2, 1) (2, 5) (2, 10) ... etc. Let cost of each edge is 42. Let
d[U][V] = inf
,d[(i, 1)][(i+1, 1)] = 1
,d[(i, 1)][(i, 5)] = 5-1
,d[(i, 5)][(i, 10)] = 10-5
,d[(i,5)][(i+1,10)] = 42
, and don't forget — graph is bidirectional i.e.d[U][V] == d[V][U]
.will you more explore the query part of problem(last statement of your post) ?, as total vertices are N+(2*M) and vertices present in query might not be in those N+(2*M) vertices.
Ок, for example have 100 towers. in tower 5 there is bridges on floors 13 and 25, in tower 42 there is bridges on floors 73, 99, 200. for this two towers there will be 7 vertices of our graph (towerId, floor): (1, 1) (1, 13) (1, 25) (42, 1) (42, 73) (42, 99) (42, 200). the is an query (1, 19) (42, 87) for first point there is two nearest vertices: (1, 13) (1, 25). for the second (42, 73) (42, 99) chek all possible ways (1, 13) -> (42, 73), (1, 25) -> (42, 73), (1, 13) -> (42, 99), (1, 25) -> (42, 99)
@Alias what to do after finding these paths ?
select best one
I assume you meant (5, 1), (5, 13), and (5, 25) for the first 3 nodes?
no of vertices will be at most 2*(N+M)
How come? From what i understand we represent the first floor of each tower by a vertice. Since there are n towers so we have n vertices at the moment. Now for each, bridge if the vertice is not already present, we add the vertices. Since there are m possible bridges. The no of distinct vertices to be added can be 2*m, since each query can have two new vertices.
So the total number of vertices can be at max n+2*m