AT_abc061_d [ABC061D] Score Attack

有一个包含 $N$ 个顶点和 $M$ 条带权有向边的有向图。 第 $i$ 条边（$1 \leq i \leq M$）连接顶点 $a_i$ 到顶点 $b_i$，权值为 $c_i$。 利用这个图和棋子，进行如下的一人游戏。 最开始，将棋子放在顶点 $1$，玩家的分数为 $0$。 玩家可以按照以下规则不断移动棋子： - 当棋子在顶点 $a_i$ 时，可以通过第 $i$ 条边移动到顶点 $b_i$。移动后，玩家的分数增加 $c_i$。 只有当棋子在顶点 $N$ 时，游戏才能结束。 保证在给定的有向图中，存在从顶点 $1$ 到顶点 $N$ 的路径。 当玩家采取使游戏结束时分数尽可能大的策略时，游戏结束时的分数会是多少？ 如果游戏结束时的分数可以无限大，请输出 `inf`。

输入以如下格式从标准输入读入： > $N$ $M$ > $a_1$ $b_1$ $c_1$ > $a_2$ $b_2$ $c_2$ > $\vdots$ > $a_M$ $b_M$ $c_M$

如果游戏结束时的分数可以无限大，输出 `inf`；否则输出游戏结束时分数的最大值。

## 限制条件 - $2 \leq N \leq 1000$ - $1 \leq M \leq \min(N(N-1), 2000)$ - $1 \leq a_i, b_i \leq N\ (1 \leq i \leq M)$ - $a_i \neq b_i\ (1 \leq i \leq M)$ - $a_i \neq a_j$ 或 $b_i \neq b_j\ (1 \leq i < j \leq M)$ - $-10^9 \leq c_i \leq 10^9\ (1 \leq i \leq M)$ - $c_i$ 为整数。 - 给定的图保证存在从顶点 $1$ 到顶点 $N$ 的路径。 ## 样例解释 1 将棋子移动到顶点 $N=3$ 的路径有以下两种： - 顶点 $1$ → 顶点 $2$ → 顶点 $3$：分数 $4+3=7$ - 顶点 $1$ → 顶点 $3$：分数 $5$ 因此，游戏结束时分数的最大值为 $7$。 ## 样例解释 2 通过不断执行“顶点 $1$ → 顶点 $2$ → 顶点 $1$ → 顶点 $2$ …”的操作，可以让游戏结束时的分数无限增加。 由 ChatGPT 4.1 翻译