P1807 Longest Path

Let $G$ be a weighted directed acyclic graph with $n$ vertices, labeled from $1$ to $n$. Design an algorithm to compute the longest path from $1$ to $n$ in $G$.

The first line contains two integers, the number of vertices $n$ and the number of edges $m$. Lines $2$ to $(m + 1)$ each contain three integers $u, v, w$ ($u

Output a single integer on one line, representing the length of the longest path from $1$ to $n$. If $1$ cannot reach $n$, output $-1$.

Constraints - For $20\%$ of the testdata, $n \leq 100$, $m \leq 10^3$. - For $40\%$ of the testdata, $n \leq 10^3$, $m \leq 10^{4}$. - For $100\%$ of the testdata, $1 \leq n \leq 1500$, $0 \leq m \leq 5 \times 10^4$, $1 \leq u, v \leq n$, $-10^5 \leq w \leq 10^5$. Translated by ChatGPT 5