TLE '17 Contest 6 P5 - Speedrunning

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 0.5s
Python 1.5s
Memory limit: 256M
Python 512M

Author:
Problem types
Speedrunning can be interesting.

Leon is speedrunning a video game, intending to reach all of the possible endings.

The entire game can be mapped out as a rooted tree of N checkpoints connected by one-way routes. Route i connects checkpoint u_i to v_i, and playing through this route takes exactly t_i seconds. Let checkpoint 1 represent the beginning of the game; all other checkpoints are reachable through some set of particular routes.

Note that a checkpoint that branches off into multiple other checkpoints represents a point in the game where Leon must make a key decision that will alter the course of the game. Furthermore, a checkpoint that leads to nowhere else (a dead-end) represents an ending.

The game also features a built-in save/load mechanic. Leon is allowed to save the game only at checkpoints, which keeps track of his current point in the game. He may choose to load the save file at any time, immediately bringing him back to the saved checkpoint. Additionally, he also has the power to reset the game at any time, which instantly takes him all the way back to the beginning (checkpoint 1).

This save/load mechanic would have made his play-through a lot easier if it weren't for the game's inconsiderate developers - only providing one save slot. If Leon plays the game optimally, what would the minimum time taken to complete the game (i.e. visit all the checkpoints) be?

Constraints

1 \le u_i < v_i \le N

1 \le t_i \le 10^9

Subtask Percentage Additional Constraints
1 10 2 \le N \le 7
2 20 2 \le N \le 12
3 30 2 \le N \le 80
4 40 2 \le N \le 5000

Input Specification

The first line contains integer N: the number of checkpoints in the game.

The following N-1 lines each contain three integers: u_i, v_i, and t_i. This represents a one-way route taking t_i seconds to play from checkpoint u_i to v_i.

Output Specification

A single integer: the minimum amount of time required to complete the entire game.

Sample Input 1

7
1 2 1
1 3 1
2 4 1
2 5 1
3 6 1
3 7 1

Sample Output 1

6

Sample Input 2

15
1 2 2
1 3 1
2 4 1
2 5 1
3 6 2
3 7 2
4 8 2
4 9 2
5 10 2
5 11 2
6 12 1
6 13 1
7 14 1
7 15 1

Sample Output 2

23

Comments


  • 2
    echofox  commented on Feb. 18, 2019, 7:38 p.m.

    what in the name of all that is good and holy is that bowser