LastTry's blog

By LastTry, history, 6 years ago, In English

Hey, guys!

I've been working on a problem recently but I need some help with the idea of it. Here it is:

You are given a directed acyclic graph with the length of the edges between two vertices. What you have to do is find the longest path in the graph, starting from the beginning vertex (it's 1). The input contains on the first line the number of vertices (N) and number of edges (M). Then it is followed by M lines, each of whom contains 3 numbers — the first 2 are the indexes of the two vertices which are connected and the 3rd number is the length of the edge between them. The output should contain the longest path in the DAG.

Example input:

5 8 1 2 5 1 4 4 1 5 1 2 3 3 2 5 1 4 3 2 5 3 3 5 4 2

Example output:

10

Explanation: Here's the path in this case: 1 2 5 4 3

Read more »

 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it