Question:
Sherlock has been led to a massive trap by his archenemy Jim Moriairty.
The trap is in the form of a graph of N Nodes, and M edges. Each of the nodes in this trap is either colored BLUE or RED.
Each edge in this trap has a duration associated with it.
He is currently at node 1, and has to reach node N to escape the trap.
Sherlock has to anyhow figure out a way to escape from this vicious trap in the minimum time possible.
However, nothing is so simple with Moriarty’s traps. He gives Sherlock a value K as well.
Sherlock needs to ensure that |X-Y| <= K, where X = number of BLUE nodes chosen along the path, Y = number of RED nodes chosen along the path.
In other words, Sherlock needs to find the minimum time to exit the trap, provided the absolute difference of blue and red nodes chosen along the path is at most K.
INPUT:
First Line comprises three space-separated integers N, M, and K.
M lines follow.
Each of them comprises 3 space-separated integers U, V, L which denotes that there is a unidirectional edge from node U to node V having a time duration L.
The next line comprises N space-separated integers. Each integer is either 0 or 1. The blue nodes are denoted by 0, whereas red nodes are denied by 1.
Output:
Print an integer denoting the minimum time to escape the trap under the given constraints. In case no path exists, print “-1” (without quotes).
Constraints:
1 <= N <= 10^3
1 <= M <= 10^4
1 <= K <= N
1 <= U, V <= N, U != V
1 <= L <= 10^3
The trap doesn’t comprise multiple edges or loops. Also, it does not comprise any directed cycles.
Sample Input:
6 6 2
2 3 1
1 2 1
4 3 2
5 6 2
1 4 2
3 5 2
1 0 1 0 1 0
Sample Output:
6
I used a basic DFS approach keeping a count of the number of red and blue nodes encountered so far but was able to pass only 1 test case of 15 test cases. (All others were TLE).
Would be great if someone gave a better approach to this question!