## CCO '15 P2 - Artskjid

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

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, , such that there is a road from to for each .

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

#### Input Specification

The first line of input contains two integers , the total number of cities and the number of roads connecting the cities (; ). There is at most one road from any given city to any other given city. Cities are numbered from to , with being Troy's starting city, and being his destination.

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

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

#### Output Specification

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

#### Sample Input

3 3
0 2 5
0 1 4
1 2 3

#### Output for Sample Input

7

#### Explanation of Output for Sample Input

The shortest route would be to take the road directly from to , of length km. The route going from to to is km, which is longer.

• commented on July 12, 2021, 9:29 a.m.

is this graph acyclic

• commented on July 12, 2021, 5:33 p.m. edit 3

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on July 12, 2021, 3:26 p.m.

Given the contraints that can be (which is that every city has a road to every other city), probably no.

• commented on Nov. 26, 2020, 7:48 p.m.

I just figured out that the title is Dijkstra backwards lol

• commented on July 24, 2020, 4:17 p.m.

Can this problem be solved in polynomial time?

• commented on July 24, 2020, 6:43 p.m.

No. (assuming that P is not NP)

• commented on July 24, 2020, 6:32 p.m. edited

Most likely no, since all the submissions to this problem are in exponential time.

Edit: I'm stupid and thought exponential time was polynomial.

• commented on Aug. 29, 2018, 6:52 p.m.

TFW you think the roads aren't one-directional

• commented on Dec. 28, 2018, 9:11 p.m.

TFW you read this comment and still make the same mistake

• commented on Nov. 17, 2020, 6:17 p.m.

• commented on Jan. 27, 2018, 11:41 p.m.

TLE

I am TLEing on Test case #8, even though my solution works on both the CCC Online Grader and PEG Judge. Is the judge running slower today?

• commented on Oct. 28, 2017, 12:29 p.m.

Java 7 and 9 are currently down; try using Java 8.

• commented on Dec. 12, 2015, 2:01 p.m.

:)