[USACO10OPEN] Water Slides G

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 E (1 <= E <= 150,000) mini slides connecting V (2 <= V <= 50,000) small pools conveniently labeled 1..V. Every mini slide must be traversed in its proper direction and may not be traversed backwards. The cows start at pool number 1 and traverse successive mini slides until they end up in the pool number V, the final pool. Every pool (except 1, the first one) includes at least one mini slide entering it and (except V, the last one) at least one (different) mini slide exiting it. Furthermore, a cow can reach the end of the ride (pool V) 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 P\_i to pool Q\_i (1 <= P\_i <= V; 1 <= Q\_i <= V; P\_i != Q\_i) and has an associated fun value F\_i (0 <= F\_i <= 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 K (1 <= K <= 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 1). 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 3 pools (pool id's shown in brackets) and four mini slides; K has the value 1 (fun values shown outside of brackets): [1] / \ 5 -> / \ <- 9 / \ [2]---3---[3] \_\_5\_\_/ She alway starts at pool 1 and ends and pool 3. If she had her way, she'd ride direct from pool 1 to pool 2 and then on the higher-fun mini slide (with fun value 5) to slide 3 for a total fun value of 5+5=10. But, if she loses control at pool 1, she might slide directly from pool 1 to pool 3 for total fun 9. If she loses control at pool 2, she could reduce her total fun to just 5+3 = 8. Bessie wants to find the most fun she can have so she strives to choose 1->3 for a total fun of 9. If she loses control at pool 1 and ends up on mini slide 1->2, she knows she will not lose control at pool 2 and will end up with fun 10. Thus, she knows her minimum fun will always be at least 9. 受到秘鲁的马丘比丘的新式水上乐园的启发，Farmer John决定也为奶牛们建一个水上乐园。当然，它最大的亮点就是新奇巨大的水上冲浪。 超级轨道包含 E (1 <= E <=150,000)条小轨道连接着V (V <= 50,000)个水池，编号为1..V。每个小轨道必须按照特定的方向运行，不能够反向运行。奶牛们从1号水池出发，经过若干条小轨道，最终到达V号水池。每个水池(除了V号和1号之外，都有至少一条小轨道进来和一条小轨道出去，并且，一头奶牛从任何一个水池到达V号水池。最后，由于这是一个冲浪，从任何一个水池出发都不可能回到这个水池) 每条小轨道从水池P\_i到水池Q\_i (1 <= P\_i <= V; 1<= Q\_i <= V; P\_i != Q\_i)，轨道有一个开心值F\_i (0 <= F\_i <= 2,000,000,000)，Bessie总的开心值就是经过的所有轨道的开心值之和。 Bessie自然希望越开心越好，并且，她有足够长的时间在轨道上玩。因此，她精心地挑选路线。但是，由于她是头奶牛，所以，会有至多K (1 <= K <= 10)次的情况，她无法控制，并且随机从某个水池选择了一条轨道(这种情况甚至会在1号水池发生) 如果Bessie选择了在最坏情况下，最大化她的开心值，那么，她在这种情况下一次冲浪可以得到的最大开心值是多少？

\* Line 1: Three space separated integers: V, E, and K \* Lines 2..E + 1: Line i+1 contains three space separated integers: P\_i, Q\_i, and F\_i

\* Line 1: 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