Problem Description

This problem is translated from CCO 2015 Day 1 T2 “Artskjid”.

You can use many algorithms to find the shortest path from one place to another. People install GPS devices in their cars, and then their phones tell them the fastest way to reach the destination. However, when on vacation, Troy likes to travel slowly. He wants to find the longest path to the destination so that he can see many new and interesting places along the way.

Therefore, a valid path consists of a sequence of distinct cities $c_1,c_2,\ldots,c_k$, and for each $1\le i<k$, there is a road from $c_i$ to $c_{i+1}$.

He does not want to visit any city more than once. Please help him find the longest path.

Input Format

The first line contains two integers $n,m$, representing the number of cities and the number of roads between cities. There is at most one road between any pair of cities. Cities are numbered from $0$ to $n-1$. Troy starts at city $0$, and city $n-1$ is his destination.

The next $m$ lines each contain three integers $s,d,l$. Each triple indicates that there is a directed road of length $l$ from city $s$ to city $d$. Each road is one-way: you can only travel from $s$ to $d$, not in the reverse direction. It is guaranteed that there is a path from city $0$ to city $n-1$.

Output Format

Output one integer: the length of the longest path that starts at city $0$ and ends at city $n-1$, without visiting any city more than once. The path length is the sum of the lengths of the roads used.

3 3
0 2 5
0 1 4
1 2 3

7

Hint

The shortest path is to take the road directly from city $0$ to city $2$, with length $5$ km. The longest path is $0 \to 1 \to 2$, with length $4+3=7$ km.

For at least $30\%$ of the testdata, $n\le 8$.

For $100\%$ of the testdata, $2\le n \le 18$, $1\le m \le n^2-n$, $0\le s,d \le n-1$, $s\neq d$, $1\le l\le 10000$.

Translated by ChatGPT 5