-1
$\begingroup$

i have a directed graph. Basically, i have to find how many edges i need to change to opposite direction to make a path between 1 and n. So, i tried solving it by making the graph undirected and marking the directions as -1 or +1 and then going through all paths and finding which paths has minimum -1(s). I store graph data in adjacency list (because number of edges can be large) and perform dfs. I also stop travelling a path if its count of -1(s) is more than the previous minimum. I also stored in every element the previous count of -1(s) to reach it from start. and i stop if current count is more. If less, i update it and move on this path and update if the new count is minimum. But this approach is slow. What else can i try?

$\endgroup$
  • 2
    $\begingroup$ I think contests are designed to be solved on your own. $\endgroup$ – Raphael Aug 8 '14 at 9:30
2
$\begingroup$

Construct a weighted directed graph as follows. For each edge (u,v), there are an edge (u,v) of weight 0 and an edge (v,u) of weight one. Then, there is an path from 1 to n of weight k iff we can change direction of k edges to make a path. Thus, the problem can be solved by a shortest path algorithm. Since the edge weights are either 0 or 1, it can also be solved by BFS.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.