5324. 高分（High Score）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 你正在玩一个包含 `n` 个房间和 `m` 条隧道的游戏。初始分数为 `0`，每次通过隧道会使分数增加 `x`（`x` 可能为正或负）。你可以多次通过同一条隧道。 你的任务是从房间 `1` 走到房间 `n`，求可能获得的最大分数。 ## 输入格式 第一行包含两个整数 `n` 和 `m`：分别表示房间数量和隧道数量。房间编号为 `1, 2, \dots, n`。 接下来的 `m` 行描述隧道，每行包含三个整数 `a`, `b`, 和 `x`：表示从房间 `a` 到房间 `b` 的单向隧道，通过后分数增加 `x`。 **你可以假设从房间 1 到房间 n 至少存在一条路径。** ## 输出格式 输出一个整数：表示可获得的最大分数。若可以获得无限大的分数（例如存在正环且可到达终点），则输出 `-1`。 ## 输入输出样例 ### 输入 #1 ``` 4 5 1 2 3 2 4 -1 1 3 -2 3 4 7 1 4 4 ``` ### 输出 #1 ``` 5 ``` ## 说明/提示 ### 数据规模与约定 - 1 \le n \le 2500 - 1 \le m \le 5000 - 1 \le a, b \le n - -10⁹ \le x \le 10⁹