395. Longest Path in a Directed Acyclic Graph

Given a directed acyclic graph with n vertices (0-indexed) and m weighted edges (each u, v, weight), and a source and destination vertex, find the length (sum of edge weights) of the longest path from source to destination. Print 'NA' if destination is not reachable from source.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains three integers u v w, a directed weighted edge. This is followed by a line with the source vertex and a line with the destination vertex. Output: Print a single integer - the length of the longest path from source to destination, or 'NA' if destination is unreachable.

1 <= n <= 10^5

Longest path is genuinely NP-hard in GENERAL graphs (as seen in 'Longest Possible Route in a Matrix With Hurdles' from the Backtracking category, needing exhaustive search) - but becomes efficiently solvable in POLYNOMIAL time specifically because a DAG has no cycles to complicate things, a crucial distinction.

Find the length of the longest path between two vertices in a DAG. Brute force: Try every possible path from source to destination directly and find the longest one - this can be exponential for graphs with many possible paths, when a single topological-order DP pass computes it directly. Optimised: Processing vertices in topological order guarantees that by the time you compute a vertex's longest distance, EVERY prerequisite (ancestor) has already been finalized - this lets a single linear pass compute the correct longest-path DP values, taking the MAXIMUM (not overwriting) whenever multiple incoming edges could contribute to the same vertex.

Compute a topological order of the DAG (e.g. via Kahn's algorithm using in-degree counting), then process vertices in that order, maintaining a dist[] array initialized to negative infinity except dist[source] = 0, relaxing dist[u] = max(dist[u], dist[v] + w) for every edge (v, u, w) as v is processed. Because topological order guarantees every predecessor of a vertex is finalized before the vertex itself is processed, one linear pass over vertices and edges is enough, with no recursion at all. This matters in practice for n up to 10^5, since the memoized recursive version risks a stack overflow on a long chain of vertices, while this iterative version has no such risk. Time: O(n+m) Space: O(n)

Starting from the source, recursively explore every outgoing edge and follow every possible path to the destination, keeping track of the running weight sum and recording the maximum total seen whenever the destination is reached. This directly enumerates every source-to-destination path so it is trivially correct, but in a DAG the number of distinct paths between two vertices can itself grow exponentially with the number of vertices, since the same intermediate vertex can be reached via many different upstream paths that all get explored independently. Time: O(2^n) worst case Space: O(n)

Define longest(v) as the length of the longest path from v to the destination, computed recursively as the maximum over all edges (v, u, w) of w + longest(u), with longest(destination) = 0. Cache the result for each vertex the first time it is computed, so that when multiple upstream paths reach the same vertex, its longest-path-to-destination value is only ever computed once instead of once per incoming path. This collapses the exponential path enumeration of brute force down to one recursive evaluation per vertex, plus one edge relaxation per edge. Time: O(n+m) Space: O(n)

1. Process vertices in TOPOLOGICAL ORDER (guaranteed possible since it's a DAG). 2. A vertex's longest distance from the source is the MAXIMUM, over all its incoming edges (u,v,w), of (longest distance to u) + w. 3. Start every vertex's value at negative infinity except the source (which starts at 0) - a vertex still at negative infinity when reached is simply unreachable from the source, and its outgoing edges should be skipped.

Time: O(n + m) - a topological sort plus one relaxation pass over all edges. Space: O(n), for the longest-distance array and the topological order.

Test destination unreachable from source (print 'NA'), source equal to destination (length 0), and n at the upper bound of 10^5.

Be ready to connect this to shortest-path DP on a DAG - it's the EXACT same technique, just taking a MAXIMUM instead of a MINIMUM at each relaxation step, since a DAG's acyclic structure makes both directions equally straightforward (unlike general graphs, where longest path is NP-hard).