PEG Judge - CCO15

2015 Canadian Computing Olympiad

Day 1, Problem 2 - Artskjid

There are many well-known algorithms for finding the shortest route from one location to another. People have GPS devices in their cars and in their phones to show them the fastest way to get where they want to go. While on vacation, however, Troy likes to travel slowly. He would like to take the longest route to his destination so that he can visit many new and interesting places along the way.

As such, a valid route consists of a sequence of distinct cities c₁, c₂, …, c_k, such that there is a road from c_i to c_i+1 for each 1 ≤ i < k.

He does not want to visit any city more than once. Can you help him find the longest route?

Input Format

The first line of input contains two integers n, m, the total number of cities and the number of roads connecting the cities (2 ≤ n ≤ 18; 1 ≤ m ≤ n² − n). There is at most one road from any given city to any other given city. Cities are numbered from 0 to n − 1, which 0 being Troy's starting city, and n − 1 being his destination.

The next m lines of input each contain three integers s, d, l. Each triple indicates that there is a one way road from city s to city d of length l km (0 ≤ s ≤ n − 1; 0 ≤ d ≤ n − 1; s ≠ d; 1 ≤ l ≤ 10000). Each road is one-way: it can only be taken from s to d, not vice versa. There is always at least one route from city 0 to city n − 1.

For at least 30% of the marks for this problem, n ≤ 8.

Output Format

Output a single integer, the length of the longest route that starts in city 0, ends in city n − 1, and does not visit any city more than once. The length is the sum of the lengths of the roads taken along the route.