Questions Tagged With helphttps://discuss.codechef.com/tags/help/?type=rss&user=AnonymousBunnyquestions tagged <span class="tag">help</span>enSun, 30 Aug 2015 22:30:22 +0530finding shortest path in a graph with good and bad edgeshttps://discuss.codechef.com/questions/74583/finding-shortest-path-in-a-graph-with-good-and-bad-edges<p>Hi everyone!</p>
<p>I've been stuck on this problem for a while: <a href="http://wcipeg.com/problem/ccc11s2p2">http://wcipeg.com/problem/ccc11s2p2</a></p>
<p>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).</p>
<p>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.</p>
<p>Any help will be appreciated. Thanks :)</p>AnonymousBunnySun, 30 Aug 2015 22:30:22 +0530https://discuss.codechef.com/questions/74583/finding-shortest-path-in-a-graph-with-good-and-bad-edgesgraphdijkstrahelpshortest-path