No submission language available for this problem.

题目描述

公元 2070 年，人类在火星上建造的数个太空基地，太空基地的编号为 1 至 n，每个太空基地之间有 m 单向连通的道路，宇航员走每条路都会消耗太空服中的氧气，幸运的是，太空基地之间有免费的泊船，不仅不消耗氧气，还可以补回氧气。问从 s 基地移动到 t 基地最少消耗多少氧气。

数据确保可从 s 移动到 t

输入格式

第一行四个由空格隔开的整数，分别表示 n，m，s，t ;

之后的 m 行，每行三个正整数 x，y，z，表示一条从 x 到 y 长度为 z 的单向边：

• 若 z>0 表示消耗氧气
• 若 z<0 表示可以搭船并恢复 -z 氧气。

输出格式

一个整数表示氧气的消耗数

5 5 1 5
1 2 5
1 3 7
3 5 1 
1 4 10 
4 5 -4

8

Explain

从 1 到 5 有两条路径：

1. 1->3->5 : 7 + 1 = 8
2. 1->4->5 : 10 + 0 = 10

显然消耗最少的是第一条路

数据范围

$1 <= n <= 10000$

$0 <= m <= min(n * (n - 1), 20000)$

$|氧气消耗| <= 20$