Tensor's blog

DAG problem .. help ?
By Tensor, 12 years ago, In English

I had been solving this problem

this is my code so far ... any help would be appreciated.

thanks in advance.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
12 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Let Level(X) will be index of vertice X in some topologically sorted vector of vertices. DP(x1, x2, x3) — maximum possible length of 3-path (x1, x2, x3) -> (t1, t2, t3). to calculate DP(x1, x2, x3) you shuld try to move from some of three vertices (x1, x2, x3) with minimum Level.

UPD: vertices are already topologically sorted, Level(x) == x.

→ Reply