High Score

题目描述

你玩一个由 $n$ 个房间和 $m$ 条隧道组成的游戏。你的初始分数为 0，每条隧道会使你的分数增加 $x$，其中 $x$ 可以为正也可以为负。你可以多次经过同一条隧道。 你的任务是从房间 1 走到房间 $n$。你最多可以获得多少分？

输入格式

输入的第一行包含两个整数 $n$ 和 $m$：房间数和隧道数。房间编号为 1,2,$\dots$, $n$。 随后有 $m$ 行描述隧道。每行包含三个整数 $a$, $b$ 和 $x$：隧道从房间 $a$ 开始，到达房间 $b$，并使你的分数增加 $x$。所有隧道都是单向的。 你可以假定从房间 1 可以到达房间 $n$。

输出格式

输出一个整数：你最多可以获得的分数。如果你可以获得任意大的分数，则输出 -1。

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

5

提示

$1 \le n \le 2500$ $1 \le m \le 5000$ $1 \le a,b \le n$ $-10^9 \le x \le 10^9$

标签: CSES1673|图论

来源

CSES1673|图论