finding shortest path in a graph with good and bad edges

help
, , ,
1

Hi everyone!

I’ve been stuck on this problem for a while: PEG Judge - CCC11 Stage 2 - Vampire Tunnels

Basically, you’re given a weighted undirected graph with n vertices and m edges (n<=1600, m<=10^5) where some of the edges are good and others bad. You have to find the shortest path between two vertices among all such paths whose sum of weights of bad edges is at most a given threshold S (S<=3600).

I tried modifying Dijsktra’s algorithm (add a vertex to the visited set only if the sum of bad edges on the path from the source to that vertex is at most S)- but it’s not too hard to find testcases for which this fails.

Any help will be appreciated. Thanks :slight_smile:

2

I would suggest a DP for that matter: DP[node][bad_sum] -> the minimum path to the “node” vertex using bad edges of sum bad_sum <= S. You can then implement a Dijkstra (or Bellman-Ford) algo to fill the matrix, i.e.:

You keep a min heap that keeps two parametres (the vertex “node” and the bad sum “bad_sum”, and at each time pop the min and push the adjacent cells (if you augment the DP matrix). This Works only if edges have positive costs. If they can have negative cost, then you’re stuck with Bellman-Ford. Good luck!

1 Like
3

One thing. m<= 10^4, not 10^5 :wink:

4

(sorry for the late reply) Yes, the edges are positive :slight_smile: I don’t entirely understand the “augmenting the matrix” part, but I think I get the basic idea. Thanks! :slight_smile:

5

By “augmenting the matrix” I was just saying that we “make it a little better” by changing its value into a smaller one :).