「JoyOI1136」火焰巨魔的惆怅

2014年1月28日2,7040
背景 Background
JoyOI2月月赛第一道
巨魔家族在某天受到了其他种族的屠杀,作为一个英雄,他主动担任了断后的任务,但是,在巨魔家族整体转移过后,火焰巨魔却被困住了,他出逃的方式也只有召唤小火人这一种方式,所以请你帮助他。
描述 Description
我们把火焰巨魔所处的位置抽象成一张有向图,他的位置就是1号点位,目的就是走到第N号点位,因为小火人会裂嘛,所以我们可以看做每走一条路,小火人的数量都会加倍,而每条路上的敌人有多强,会消耗多少小火人c[i]也会给出(c[i]为负值);当然有些时候路上也会遇到魔法泉之类的东西,这时候就可以补充一些小火人咯(c[i]为正值)。如果小火人死光了,那么火焰巨魔也就可以看做是挂了,毕竟智力型英雄就是脆啊。希望你帮助火焰巨魔用最少的初始小火人逃离这次屠杀。
输入格式 InputFormat
第一行两个数N(<=50000),M(<=100000)表示点位数与边数。
一下M行,每行三个数a,b,c表示a,b两点间的边权是c(|c|<=10000)
输出格式 OutputFormat
输出仅一个整数,表示最小初始小火人数。
输入格式 InputFormat

5 4
1 2 -3
1 3 -6
3 4 1
4 5 -9

样例输出 SampleOutput

4

数据范围和注释 Hint
初始小火人为4个,到3点剩2个,到4变成5个,到5剩1个。
所以初始最少为4,更少的小火人是不足以走到5号点位的。
代码

 

avatar
  Subscribe  
提醒