P2991 [USACO10OPEN] Water Slides G

受到秘鲁马丘比丘新建水上乐园的启发，约翰农夫决定为奶牛们建造一个水上乐园。其最大的吸引力将是一个设计独特的巨型滑梯。超级滑梯由 $E(1 \le E\le150,000)$ 个迷你滑梯连接 $V(2\le V\le50,000)$ 个小水池，这些水池被方便地标记为 $1$ 到 $V$。每个迷你滑梯必须按照正确的方向滑行，不能逆向滑行。奶牛们从编号为 $1$ 的水池出发，依次滑过迷你滑梯，直到到达编号为 $V$ 的终点水池。每个水池（除了第一个水池 $1$）至少有一个迷你滑梯进入它，（除了最后一个水池 $V$）至少有一个（不同的）迷你滑梯从它出去。 此外，奶牛可以通过一系列迷你滑梯从任何水池到达终点水池 $V$。最后，由于这是一个滑梯，不可能离开一个水池后，再经过一系列迷你滑梯后重新回到该水池。 每个迷你滑梯 $i$ 从水池 $P_i$ 到水池 $Q_i$ （$1\le P_i\le V; 1\le Q_i\le V; P_i\ne Q_i$），并且有一个与之关联的乐趣值 $F_i(0\le F_i\le 2,000,000,000)$。对于任何一次超级滑梯的滑行，贝茜的总乐趣是所有经过的迷你滑梯的乐趣值之和。 贝茜自然希望在滑梯排队等待的漫长时间里尽可能多地享受乐趣。通常，她会仔细选择从每个水池出来的迷你滑梯。然而，她是一头奶牛，在滑下滑梯的过程中最多有 $K(1\le K\le 10)$ 次会失去控制，随机选择一个迷你滑梯离开水池（这甚至可能发生在水池 $1$）。 如果贝茜选择以最坏情况下最大化她的乐趣，她在给定的超级滑梯上能保证获得多少乐趣？ 例如，考虑一个有 $3$ 个水池（水池编号如括号中所示）和四个迷你滑梯的小型乐园；$K$ 的值为 $1$（乐趣值如括号外所示）： [1] / \ 5 -> / \

\* 第 $1$ 行：三个用空格分隔的整数：$V$，$E$ 和 $K$。 \* 第 $2$ 行到第 $E+1$ 行：第 $i+1$ 行包含三个用空格分隔的整数：$P_i$，$Q_i$ 和 $F_i$。

\* 第 $1$ 行：一个整数，表示贝茜可以保证获得的最小乐趣。

（由 ChatGPT 4o 翻译）