You are not logged in. Please login at www.codechef.com to post your questions!

×

finding shortest path in a graph with good and bad edges

0
1

Hi everyone!

I've been stuck on this problem for a while: http://wcipeg.com/problem/ccc11s2p2

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 :)

asked 30 Aug '15, 22:30

AnonymousBunny's gravatar image

5★AnonymousBunny
15718
accept rate: 10%

One thing. m<= 10^4, not 10^5 ;)

(31 Aug '15, 00:25) nibnalin6★

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!

link

answered 30 Aug '15, 23:55

retrograd's gravatar image

6★retrograd
1503
accept rate: 12%

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

(02 Sep '15, 12:36) AnonymousBunny5★

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

(03 Sep '15, 14:23) retrograd6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,698
×1,197
×164
×125

question asked: 30 Aug '15, 22:30

question was seen: 2,632 times

last updated: 03 Sep '15, 14:23