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