← 返回题目列表

AtCoder · abc061_d

D. 得分攻击

中文机器翻译题面 查看原题

分数: 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