CCO '15 P2 - Artskjid - DMOJ: Modern Online Judge

CCO '15 P2 - Artskjid

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 1G

Problem types

Canadian Computing Olympiad: 2015 Day 1, Problem 2

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_1, c_2, \dots, c_k$ ~c_1, c_2, \dots, c_k~, such that there is a road from $c_i$ ~c_i~ to $c_{i+1}$ ~c_{i+1}~ for each $1 \le i < k$ ~1 \le i < k~.

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 $n, m$ ~n, m~, the total number of cities and the number of roads connecting the cities ( $2 \le n \le 18$ ~2 \le n \le 18~; $1 \le m \le n^2 - n$ ~1 \le m \le n^2 - n~). There is at most one road from any given city to any other given city. Cities are numbered from $0$ ~0~ to $n-1$ ~n-1~, with $0$ ~0~ being Troy's starting city, and $n-1$ ~n-1~ being his destination.

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

For at least 30% of the marks for this problem, $n \le 8$ ~n \le 8~.

Output Specification

Output a single integer, the length of the longest route that starts in city $0$ ~0~, ends in city $n-1$ ~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.

Sample Input

Output for Sample Input

Explanation of Output for Sample Input

The shortest route would be to take the road directly from $0$ ~0~ to $2$ ~2~, of length $5$ ~5~ km. The route going from $0$ ~0~ to $1$ ~1~ to $2$ ~2~ is $4 + 3 = 7$ ~4 + 3 = 7~ km, which is longer.

Comments

3

bariumlanthanum commented on March 16, 2022, 2:57 p.m.

Troy: wants longest route

gas prices now: NO

-21

jorgebean commented on March 15, 2022, 4:59 a.m.

This problem is impossible. Please remove it from the servers or update the statement and test cases. Thank you in advance.

This comment is hidden due to too much negative feedback. Show it anyway.

6
Badmode commented on March 15, 2022, 10:54 p.m. ← edit 3 →
Copies from geeks for geeks - https://dmoj.ca/src/4418660

Complains the question is impossible

Copies from Github - https://dmoj.ca/src/4418706

Proceeds to solve 40pp IOI problems effortlessly

-19

jorgebean commented on March 16, 2022, 12:51 a.m.

IOI questions are actually possible, hence why I can effortlessly solve them, whereas this problem is literally not possible without changing the test data.

This comment is hidden due to too much negative feedback. Show it anyway.

5

vishnus commented on March 16, 2022, 1:51 p.m.

jorgebean, you've been a sussy baka

7

Plasmatic commented on March 16, 2022, 8:34 a.m. ← edited →

Not gonna lie, to me that sounds a bit...

...farfetch'd

-3

Marshmellon commented on March 16, 2022, 2:05 a.m.

effortlessly.

5

Badmode commented on March 16, 2022, 1:50 a.m.

https://en.wikipedia.org/wiki/Gaslighting

11

maxcruickshanks commented on March 16, 2022, 1:57 a.m.

You made that article up.

3

henrybaolol9 commented on March 16, 2022, 1:48 a.m.

preach king

3

maxcruickshanks commented on March 15, 2022, 2:30 p.m.

Given that more than $400$ ~400~ people have solved this question, I doubt the test cases (or intended solutions) are wrong. If you have a specific issue with your code, you can ask for help in the DMOJ Discord server.

15

EpicChadGamer commented on March 15, 2022, 8:58 a.m.

The only impossible task is me winning your heart 😫😵

1

bariumlanthanum commented on July 12, 2021, 1:29 p.m.

is this graph acyclic

0

Badmode commented on July 12, 2021, 7:26 p.m.

Given the contraints that $m$ ~m~ can be $n^2 - n$ ~n^2 - n~ (which is that every city has a road to every other city), probably no.

24

dxke02 commented on Nov. 27, 2020, 12:48 a.m.

I just figured out that the title is Dijkstra backwards lol

2

aaronhe07 commented on July 24, 2020, 8:17 p.m.

Can this problem be solved in polynomial time?

7

d commented on July 24, 2020, 10:43 p.m.

No. (assuming that P is not NP)

3

maxcruickshanks commented on July 24, 2020, 10: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.

10

Plasmatic commented on Aug. 29, 2018, 10:52 p.m.

TFW you think the roads aren't one-directional

20

Riolku commented on Dec. 29, 2018, 2:11 a.m.

TFW you read this comment and still make the same mistake

3

ArtyKing12 commented on Nov. 17, 2020, 11:17 p.m.

I just read those two comments and my muscle memory instantly made those roads bi-directional...