分数: 400 点
问题陈述
有一个有向图 N 顶点和 M 边缘。 的 i第边缘 (1≤i≤M) 从顶点开始的点 a_i 到顶点 b_i,并且有一个权重 c_i。 我们将使用该图和一块玩以下单人游戏。
最初,该块放置在顶点 1,玩家的得分设置为 0。 玩家可以按如下方式移动棋子:
- 当棋子放置在顶点时 a_i,沿着 i第一条边到顶点 b_i。完成此动作后,玩家的分数增加 c_i.
只有当棋子放置在顶点时,玩家才能结束游戏 N。 给定的图保证可以从顶点开始遍历 1 到顶点 N.
当玩家在游戏结束时采取最佳行动以最大化分数时,分数会是多少?
如果可以无限增加分数,则打印 inf.
约束
- 2≤N≤1000
- 1≤M≤min(N(N-1),2000)
- 1≤a_i,b_i≤N (1≤i≤M)
- a_i≠b_i (1≤i≤M)
- a_i≠a_j or b_i≠b_j (1≤i<j≤M)
- -10^9≤c_i≤10^9 (1≤i≤M)
- c_i 是一个整数。
- 在给定的图中,存在一条从顶点开始的路径 1 到顶点 N.
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 c_1 a_2 b_2 c_2 : a_M b_M c_M
输出
在游戏结束时打印最大可能得分(如果有限)。如果可以无限增加分数,则打印 inf.
示例输入 1
3 3 1 2 4 2 3 3 1 3 5
示例输出 1
7
有两种方法可以将棋子移动到顶点 N=3:
- 顶点 1 → 顶点 2 → 顶点 3 :分数 4+3=7
- 顶点 1 → 顶点 3 :分数 5
因此,游戏结束时的最大可能得分是 7.
示例输入 2
2 2 1 2 1 2 1 1
示例输出 2
inf
通过在顶点之间交替可以无限地增加分数 1 和 2.
示例输入 3
6 5 1 2 -1000000000 2 3 -1000000000 3 4 -1000000000 4 5 -1000000000 5 6 -1000000000
示例输出 3
-5000000000