[NOIP2010冲刺五]汤姆斯的天堂梦

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 par.in 输出文件 par.out

【题目描述】

汤姆斯生活在一个等级为0的星球上。那里的环境极其恶劣,每天12小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为N的星球上天堂般的生活。

有一些航班将人从低等级的星球送上高一级的星球,有时需要向驾驶员支付一定金额的费用,有时却又可以得到一定的金钱。

汤姆斯预先知道了从0等级星球去N等级星球所有的航线和需要支付(或者可以得到)的金钱,他想寻找一条价格最低(甚至获得金钱最多)的航线。

【输入格式】

第一行一个正整数N(N100),接下来的数据可分为N个段落每段的第一行一个整数Ki(Ki100),表示等级为i的星球有Ki个。

接下来的Ki中第Tij行依次表示与等级为i,编号为i的星球相连的等级为i-l的星球的编号和此航线需要的费用(正数表示支出,负数表示收益,费用的绝对值不超过1000)。

每行以0结束,每行的航线数≤100

【输出格式】

输出所需(或所得)费用。正数表示支出,负数表示收益。

【样例输入】

 3
 2
 1 15 0
 1 5 0
 3
 1 -5 2 10 0
 1 3 0
 2 40 0
 2
 1 1 2 5 3 -5 0
 2 -19 3 -20 0

【样例输出】

-1

【提示】

对于100%的数据N100 Ki100

【写真】