A.ElGamal's blog

shortest path problem
By A.ElGamal, history, 11 years ago, In English

544D - Destroying Roads for this problem I tried using Dijkstra and mark edges I used then I would loop on edges and count the number of unused edges then print them, but the problem is the following: 1)dijkstra gives me the "shortest" path where the problem needs that path does not exceed some fixed value so that I can delete more edges at the end 2)I can not handle the case when dijkstra select two ways for 1st and 2nd case that does not intersect (because it looks for shortest path) where it could increase the length of the path but decrease the number of used edges. any help would be appreciated

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
11 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Here's a hint:

Since Dijkstra's Algorithm runs in O(E log E) time, you should be able to find all-pairs shortest paths in O(VE log E), which runs within the time limit.

The paths not removed should form either: 1. Two distinct paths or, 2. Two paths that go s1 -- a -- b -- t1 and s2 -- a -- b -- t2, where in this case a -- b is the shared segment among the two paths.

I think this should be helpful in solving the problem.

→ Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Ok it's an unweighted graph, so you should use BFS to calculate all the shortest paths.

Maybe the first and second path would intersect, so suppose that they intersect with the segment (i,j) (from vertex i to j) so the cost for the first path will be: dist[s0][i] + dist[i][j] + dist[j][d0]

and the second path : dist[s1][i] + dist[i][j] + dist[j][d1] 

if (firstPath <= T1 && secondPath <= T2) 
     ans = min(ans, firstPath+secondPath - dist[i][j]);

Hope it helps

→ Reply