P1176 火焰巨魔的惆怅
时间: 1000ms / 空间: 131072KiB / Java类名: Main
背景
TYVJ2月月赛第一道
巨魔家族在某天受到了其他种族的屠杀，作为一个英雄，他主动担任了断后的任务，但是，在巨魔家族整体转移过后，火焰巨魔却被困住了，他出逃的方式也只有召唤小火人这一种方式，所以请你帮助他。
巨魔家族在某天受到了其他种族的屠杀，作为一个英雄，他主动担任了断后的任务，但是，在巨魔家族整体转移过后，火焰巨魔却被困住了，他出逃的方式也只有召唤小火人这一种方式，所以请你帮助他。
描述
我们把火焰巨魔所处的位置抽象成一张有向图，他的位置就是1号点位，目的就是走到第N号点位，因为小火人会裂嘛，所以我们可以看做每走一条路，小火人的数量都会加倍，而每条路上的敌人有多强，会消耗多少小火人c[i]也会给出(c[i]为负值)；当然有些时候路上也会遇到魔法泉之类的东西，这时候就可以补充一些小火人咯(c[i]为正值）。如果小火人死光了，那么火焰巨魔也就可以看做是挂了，毕竟智力型英雄就是脆啊。希望你帮助火焰巨魔用最少的初始小火人逃离这次屠杀。
输入格式
第一行两个数N（<=50000），M（<=100000）表示点位数与边数。
一下M行，每行三个数a，b，c表示a，b两点间的边权是c（|c|<=10000）
一下M行，每行三个数a，b，c表示a，b两点间的边权是c（|c|<=10000）
输出格式
输出仅一个整数，表示最小初始小火人数。
测试样例1
输入
5 4
1 2 -3
1 3 -6
3 4 1
4 5 -9
输出
4
备注
初始小火人为4个，到3点剩2个，到4变成5个，到5剩1个。
所以初始最少为4，更少的小火人是不足以走到5号点位的。from wsd TYVJ月赛出题组
所以初始最少为4，更少的小火人是不足以走到5号点位的。from wsd TYVJ月赛出题组
因为边权带负数所以很容易想到用spfa