33OJ
登录 注册

#P2991. [USACO10OPEN] Water Slides G

[USACO10OPEN] Water Slides G

Problem Description

Inspired by the new water park at Machu Picchu in Peru, Farmer John has decided to build one for the cows. Its biggest attraction is to be a giant water slide of a peculiar design. The superslide comprises EE (1≤E≤150,0001 \le E \le 150,000) mini slides connecting VV (2≤V≤50,0002 \le V \le 50,000) small pools conveniently labeled 1…V1\dots V. Every mini slide must be traversed in its proper direction and may not be traversed backwards. The cows start at pool number 11 and traverse successive mini slides until they end up in the pool number VV, the final pool. Every pool (except 11, the first one) includes at least one mini slide entering it and (except VV, the last one) at least one (different) mini slide exiting it.

Furthermore, a cow can reach the end of the ride (pool VV) from any pool by going down a sequence of mini slides. Finally, since this is a slide, it is not possible to leave a pool and then encounter that pool again after traversing some set of mini slides.

Each mini slide i runs from pool PiP_i to pool QiQ_i (1≤Pi≤V1 \le P_i \le V; 1≤Qi≤V1 \le Q_i \le V; Pi≠QiP_i \ne Q_i) and has an associated fun value FiF_i (0≤Fi≤2,000,000,0000 \le F_i \le 2,000,000,000). Bessie's total fun for any given trip down the superslide is the sum of the fun values of all the mini slides traversed.

Bessie naturally wants to have as much fun as possible, given the long time that she spends in the slide's queue waiting for the ride. Generally, she carefully chooses which mini slide to follow out of each pool. She is a cow, however, and no more than KK (1≤K≤101 \le K \le 10) times as she splashes down the slide, she loses control and follows a random mini slide out of a pool (this can even happen on pool 11).

If Bessie chooses so as to maximize her fun in the worst case, how much fun is she guaranteed to have for a given super-slide?

By way of example, consider a small park that has 33 pools (pool id's shown in brackets) and four mini slides; KK has the value 11 (fun values shown outside of brackets):

[1] /
5 -> / \ <- 9

/ \

[2]---3---[3]

__5__/

She alway starts at pool 11 and ends and pool 33. If she had her way, she'd ride direct from pool 11 to pool 22 and then on the higher-fun mini slide (with fun value 55) to slide 33 for a total fun value of 5+5=105+5=10. But, if she loses control at pool 11, she might slide directly from pool 11 to pool 33 for total fun 99. If she loses control at pool 22, she could reduce her total fun to just 5+3=85+3 = 8.

Bessie wants to find the most fun she can have so she strives to choose 11->33 for a total fun of 99. If she loses control at pool 11 and ends up on mini slide 11->22, she knows she will not lose control at pool 22 and will end up with fun 1010. Thus, she knows her minimum fun will always be at least 99.

Input Format

Line 11: Three space separated integers: VV, EE and KK.

Lines 2…E+12\dots E + 1: Line i+1i+1 contains three space separated integers: PiP_i, QiQ_i and FiF_i.

Output Format

Line 11: A single line with a single integer that is the minimum fun that Bessie can guarantee she can have.

3 4 1 
2 3 5 
1 2 5 
1 3 9 
2 3 3 

9