logo AlgoBeat OnlineJudge
登录 注册

#101916. [BZOJ 1916] [Usaco2010 Open]冲浪

内存限制:64 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

受到秘鲁的马丘比丘的新式水上乐园的启发,Farmer John决定也为奶牛们建 一个水上乐园。当然,它最大的亮点就是新奇巨大的水上冲浪。超级轨道包含 E (1

她总是从1号水池出发,抵达3号水池。如果她总是可以自己选择,就是不会发生不能控制的情况她可以选择从1到2(这条轨道开心值为5),再从2到3(开心值为5),总的开心值为5+5=10。但是,如过她在1号水池失去控制,直接到了3,那么开心值为9,如果她在2号水池失去控制,她总的开心值为8。Bessie想要找到最大化开心值的方案,可以直接从1到3,这样,如果在1号水池失去控制,这样,她就不会在2号水池失去控制了,就能够得到10的开心值。因此,她的开心值至少为9

输入格式

  • 第一行: 三个用空格隔开的整数: V, E, 和 K

  • 第2到第E+1行: 第i+1行包含三个用空格隔开的整数: P_i, Q_i, and F_i

输出格式

  • 第一样: 一行一个整数表示在最坏情况下最大化的开心值

样例

样例输入

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

样例输出

9