Longest Path in a Directed Acyclic Graph(DAG) | Problem G | Atcoder Educational DP Contest Editorial

In this video I describe how to find out the longest path in a directed Acyclic Graph (DAG), which is also the editorial of the problem G from the Atcoder Education DP Contest.

Subscribe for more content!

[bababoi]

I have been looking for a solution to this problem for a very long time, but your way is the clearest

[shivamgupta]

SIR PLZ CONTINUE UR AT CODER DP SERIES, ,FURTHER..IT HELPED ME A LOT .PLZ

[shiva_krishna_rama]

Can you plz explain some approach using pen and paper and then goes toward to code,
BTW great Content

[pleasesirmorevideos]

thanks bro just try to finish this series as soon as possible :)

[manas_singh]

Great! Instead of using visited array, you can return dp[x] early if it is already set to a non-zero value.

[psibarpsi]

What would you say the difficulty of this problem is in terms of CF?

[aman-tlgd]

hey! why do we use the concept of topological ordering if we can find the solution using DP? Is that more time efficient ?

[avikmallick]

Somehow I convinced my self to do dfs from every edge and thought that it would give TLE, but it got accepted (although dfs used memorization)

[atultyagi]

Hello Utraksh I got this challenge “Challenge One - Basic algorithms
Assume a labeled directed acyclic graph (DAG) in which nodes can have multiple ancestors and descendants and there is a single unique root node without any ancestor. In this DARG edge labels represent scores and range from zero to one. Implement a solution to the “highest scoring path problem”, that is, your implementation should find the sequence of edges (path), for which the sum of edge labels is the highest of all possible paths. Note that the problem is also known as the longest path problem and can be solved by dynamic programming for labeled DAGs. Please develop your code with unit tests that verify the correctness of your solution.
You will receive extra points if you solve this problem in Rust, Fortran, Golang, or C/C++.” Can you please give me the hint about above task to solve this problem?

[THEkarankaira]

hey on the right side how does that test0 test1 test2 is coming I also use Sublime text thats why asking??