/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
N 頂点 M 辺の重み付き有向グラフがあります。
i(1≦i≦M) 番目の辺は 頂点 a_i から 頂点 b_i を重み c_i で結びます。
このグラフと駒を利用して、次の1人ゲームを行います。
最初、駒を頂点 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 または 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 に移動できる経路は以下の 2 通りです。
- 頂点 1 → 頂点 2 → 頂点 3 : スコア 4+3=7
- 頂点 1 → 頂点 3 : スコア 5
したがって、ゲーム終了時のスコアの最大値は 7 となります。
入力例 2
2 2 1 2 1 2 1 1
出力例 2
inf
頂点 1 → 頂点 2 → 頂点 1 → 頂点 2 … と移動することで、ゲーム終了時のスコアをいくらでも増やせます。
入力例 3
6 5 1 2 -1000000000 2 3 -1000000000 3 4 -1000000000 4 5 -1000000000 5 6 -1000000000
出力例 3
-5000000000
Score : 400 points
Problem Statement
There is a directed graph with N vertices and M edges. The i-th edge (1≤i≤M) points from vertex a_i to vertex b_i, and has a weight c_i. We will play the following single-player game using this graph and a piece.
Initially, the piece is placed at vertex 1, and the score of the player is set to 0. The player can move the piece as follows:
- When the piece is placed at vertex a_i, move the piece along the i-th edge to vertex b_i. After this move, the score of the player is increased by c_i.
The player can end the game only when the piece is placed at vertex N. The given graph guarantees that it is possible to traverse from vertex 1 to vertex N.
When the player acts optimally to maximize the score at the end of the game, what will the score be?
If it is possible to increase the score indefinitely, print inf.
Constraints
- 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 is an integer.
- In the given graph, there exists a path from vertex 1 to vertex N.
Input
Input is given from Standard Input in the following format:
N M a_1 b_1 c_1 a_2 b_2 c_2 : a_M b_M c_M
Output
Print the maximum possible score at the end of the game, if it is finite. If it is possible to increase the score indefinitely, print inf.
Sample Input 1
3 3 1 2 4 2 3 3 1 3 5
Sample Output 1
7
There are two ways to move the piece to vertex N=3:
- vertex 1 → vertex 2 → vertex 3 : score 4+3=7
- vertex 1 → vertex 3 : score 5
Thus, the maximum possible score at the end of the game is 7.
Sample Input 2
2 2 1 2 1 2 1 1
Sample Output 2
inf
It is possible to increase the score indefinitely by alternating between vertex 1 and 2.
Sample Input 3
6 5 1 2 -1000000000 2 3 -1000000000 3 4 -1000000000 4 5 -1000000000 5 6 -1000000000
Sample Output 3
-5000000000