Problem:


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



Sample input:
3 3
1 2 4
2 3 3
1 3 5


Sample output:
7

Submission status: Wrong Answer

Solution code:
class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # 本来無向グラフでのみ全域木を考えるが、二重辺なら有向でも行けそう
        # d[i][i] < 0 なら、グラフは負のサイクルを持つ
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        for i in range(self.N):
            if self.d[i][i] < 0:
                hasNegativeCycle = True
                break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d


N, M = map(int, input().split())
graph = WarshallFloyd(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, True)

hasNegativeCycle, d = graph.WarshallFloyd_search()
print(-d[0][N-1])
#print(hasNegativeCycle)
#print(d)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for _ in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for src, dest, cost in edges:
        if res[dest] > res[src] + cost:
            # 今回は頂点Nが関わった場合のみ
            if dest == N-1:
                # あったら空リストを返却
                return []
    # 問題なければ頂点リストを返却
    return res

N, M = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, -c))

res = bellman_ford(N, edges, 0)

if res:
    print(-res[N-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [float('inf')] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for _ in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for src, dest, cost in edges:
        if res[dest] > res[src] + cost:
            # あったら空リストを返却
            return []
    # 問題なければ頂点リストを返却
    return res

N, M = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, -c))

res = bellman_ford(N, edges, 0)

if res:
    print(-res[N-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for i in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for src, dest, cost in edges:
        if res[dest] > res[src] + cost:
            # あったら空リストを返却
            return []
    # 問題なければ頂点リストを返却
    return res

N, M = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, -c))

res = bellman_ford(N, edges, 0)

if res:
    print(-res[N-1])
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
inf = float('INF')

class edge:
    def __init__(self, source, destination, weight):
        self.from_ = source
        self.to_ = destination
        self.weight = weight

    def values(self):
        return self.from_, self.to_, self.weight

def bellman_ford(edges, start, n):
    costs = [inf] * n
    predecessors = [-1] * n
    costs[start]= 0

    for _ in range(n-1):
        for u in range(n):
            for v,w in edges[u].items():
                if costs[v] > costs[u] + w:
                    costs[v] = costs[u] + w
                    predecessors[v] = u

    v = n-1
    while v > 0:
        u = predecessors[v]
        if costs[v] > costs[u] + w:
            return 'inf'
        v = u

    return -costs[n-1]

n,m = map(int, input().split())
edges = [{} for _ in range(n)]
for _ in range(m):
    a,b,c = map(int, input().split())
    edges[a-1][b-1] = -c
print(bellman_ford(edges, 0, n))

Submission status: Wrong Answer

Solution code:
inf = float('INF')

class edge:
    def __init__(self, source, destination, weight):
        self.from_ = source
        self.to_ = destination
        self.weight = weight

    def values(self):
        return self.from_, self.to_, self.weight

def bellman_ford(edges, start, n):
    costs = [inf] * n
    predecessors = [-1] * n
    costs[start]= 0

    for i in range(n-1):
        for e in edges:
            u,v,w = e.values()
            if costs[v] > costs[u] + w:
                costs[v] = costs[u] + w
                predecessors[v] = u

    for e in edges:
        u,v,w = e.values()
        if costs[v] > costs[u] + w:
            return 'inf'
    return -costs[n-1]

n,m = map(int, input().split())
edges = []
for _ in range(m):
    a,b,c = map(int, input().split())
    edges.append(edge(a-1, b-1, -c))
print(bellman_ford(edges, 0, n))

Submission status: Wrong Answer

Solution code:
def bellman_ford(edges, n, src):
    # n:ノード数, src:スタートノード
    # edges:edge(src, tgt, cost)のリスト
    inf = float('inf')
    dist = [inf for _ in range(n)]
    dist[src] = 0

    # 最短経路算出
    for i in range(n-1):
        for edge in edges:
            # srcにコストがあり、tgtのコストよりも低いコストで更新できそうなら
            if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]

    # 負の閉路検出
    is_cycle = False
    for edge in edges:
        if dist[edge[0]] + edge[2] < dist[edge[1]]:
            is_cycle = True
    return (dist, is_cycle)


N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a-1, b-1, -c))

d, is_cycle = bellman_ford(edges, N, 0)
if is_cycle:
    print('inf')
else:
    print(-d[N-1])

Submission status: Wrong Answer

Solution code:
def bellman_ford(edges, n, src):
    # n:ノード数, src:スタートノード
    # edges:edge(src, tgt, cost)のリスト
    inf = float('inf')
    dist = [inf for _ in range(n)]
    dist[src] = 0

    for i in range(n):
        for edge in edges:
            # srcにコストがあり、tgtのコストよりも低いコストで更新できそうなら
            if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i == n-1:
                    return -1
    return dist


N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((a, b, -c))

d = bellman_ford(edges, N, 0)
if d == -1:
    print('inf')
else:
    print(-d[N-1])

Submission status: Wrong Answer

Solution code:
"""

問題:
N 頂点 M 辺の重み付き有向グラフがあります。
i(1≦i≦M) 番目の辺は 頂点 ai から 頂点 bi を重み ciで結びます。
このグラフと駒を利用して、次の1人ゲームを行います。
最初、駒を頂点 1に置いて、プレイヤーのスコアを 0とします。
プレイヤーは、次の条件で駒を繰り返し移動させることができます。
- 頂点 aiに駒があるとき、i 番目の辺を利用して頂点 bi に移動する。移動後にプレイヤーのスコアが ci加算される。
頂点 Nに駒があるときのみ、ゲームを終了できます。
なお、与えられる有向グラフの上で頂点 1 から頂点 Nに移動できることは保障されています。
プレイヤーがゲーム終了時のスコアを出来るだけ大きくするような行動を取ったとき、ゲーム終了時のスコアはいくつになるでしょうか?
ゲーム終了時のスコアをいくらでも大きくできる場合は inf と出力してください。

制約:
- 2≦N≦1000
- 1≦M≦min(N(N−1),2000)
- 1≦ai,bi≦N(1≦i≦M)
- ai≠bi(1≦i≦M)
- ai≠ajまたは bi≠bj(1≦i<j≦M)
- −10 ** 9≦ci≦10 ** 9(1≦i≦M)
- ciは整数である。
- 与えられるグラフには、頂点 1から頂点 N への経路が存在する。

検討:
- 閉路が存在する場合、スコアをいくらでも大きくできる可能性がある
- 閉路を1周することで得られるスコア合計の符合によってinfにできるかどうかが判定可能
  - 符合が正: inf
  - 符合が0以下: 最短でNに到達したときのスコアが解
- 閉路が複数ある場合はどうするか
  - 1周したときに得られるスコア合計の符合が正かどうかで判断

必要な処理:
- 最短経路探索: ダイクストラ法? -> ベルマンフォード法（コストに正負があるため）
- 閉路を見つけ出す
- 閉路を1周したときのスコア合計

計算時間:
- ベルマンフォード法の時間計算量はO(NM)
- 解説通りにpythonで実装したらTLE判定...(約2100ms)
- 制約通りでいけば、NM = 1000 * 2000 = 2 * 10 ** 6
- 20msの化け物がいる...
"""

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append([a-1, b-1, -c])

inf = 10 ** 18
dist = [inf for _ in range(n)]
dist[0] = 0

for i in range(n-1):
    for a, b, c in edges:
        dist[b] = min(dist[b], dist[a] + c)

for i in range(n):
    for a, b, c in edges:
        if dist[a] + c < dist[b]:
            dist[b] = -inf

if inf == dist[-1]:
    print("inf")
else:
    print(-dist[-1])

Submission status: Wrong Answer

Solution code:
"""

問題:
N 頂点 M 辺の重み付き有向グラフがあります。
i(1≦i≦M) 番目の辺は 頂点 ai から 頂点 bi を重み ciで結びます。
このグラフと駒を利用して、次の1人ゲームを行います。
最初、駒を頂点 1に置いて、プレイヤーのスコアを 0とします。
プレイヤーは、次の条件で駒を繰り返し移動させることができます。
- 頂点 aiに駒があるとき、i 番目の辺を利用して頂点 bi に移動する。移動後にプレイヤーのスコアが ci加算される。
頂点 Nに駒があるときのみ、ゲームを終了できます。
なお、与えられる有向グラフの上で頂点 1 から頂点 Nに移動できることは保障されています。
プレイヤーがゲーム終了時のスコアを出来るだけ大きくするような行動を取ったとき、ゲーム終了時のスコアはいくつになるでしょうか?
ゲーム終了時のスコアをいくらでも大きくできる場合は inf と出力してください。

制約:
- 2≦N≦1000
- 1≦M≦min(N(N−1),2000)
- 1≦ai,bi≦N(1≦i≦M)
- ai≠bi(1≦i≦M)
- ai≠ajまたは bi≠bj(1≦i<j≦M)
- −10 ** 9≦ci≦10 ** 9(1≦i≦M)
- ciは整数である。
- 与えられるグラフには、頂点 1から頂点 N への経路が存在する。

検討:
- 閉路が存在する場合、スコアをいくらでも大きくできる可能性がある
- 閉路を1周することで得られるスコア合計の符合によってinfにできるかどうかが判定可能
  - 符合が正: inf
  - 符合が0以下: 最短でNに到達したときのスコアが解
- 閉路が複数ある場合はどうするか
  - 1周したときに得られるスコア合計の符合が正かどうかで判断

必要な処理:
- 最短経路探索: ダイクストラ法? -> ベルマンフォード法（コストに正負があるため）
- 閉路を見つけ出す
- 閉路を1周したときのスコア合計

計算時間:
- ベルマンフォード法の時間計算量はO(NM)
- 解説通りにpythonで実装したらTLE判定...(約2100ms)
- 制約通りでいけば、NM = 1000 * 2000 = 2 * 10 ** 6
- 20msの化け物がいる...
"""

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append([a-1, b-1, -c])

inf = 10 ** 18
dist = [inf for _ in range(n)]
dist[0] = 0

for i in range(n-1):
    for a, b, c in edges:
        dist[b] = min(dist[b], dist[a] + c)

for i in range(n):
    for a, b, c in edges:
        if dist[a] + c < dist[b]:
            dist[b] = inf

if inf == dist[-1]:
    print("inf")
else:
    print(-dist[-1])

Submission status: Wrong Answer

Solution code:
"""

問題:
N 頂点 M 辺の重み付き有向グラフがあります。
i(1≦i≦M) 番目の辺は 頂点 ai から 頂点 bi を重み ciで結びます。
このグラフと駒を利用して、次の1人ゲームを行います。
最初、駒を頂点 1に置いて、プレイヤーのスコアを 0とします。
プレイヤーは、次の条件で駒を繰り返し移動させることができます。
- 頂点 aiに駒があるとき、i 番目の辺を利用して頂点 bi に移動する。移動後にプレイヤーのスコアが ci加算される。
頂点 Nに駒があるときのみ、ゲームを終了できます。
なお、与えられる有向グラフの上で頂点 1 から頂点 Nに移動できることは保障されています。
プレイヤーがゲーム終了時のスコアを出来るだけ大きくするような行動を取ったとき、ゲーム終了時のスコアはいくつになるでしょうか?
ゲーム終了時のスコアをいくらでも大きくできる場合は inf と出力してください。

制約:
- 2≦N≦1000
- 1≦M≦min(N(N−1),2000)
- 1≦ai,bi≦N(1≦i≦M)
- ai≠bi(1≦i≦M)
- ai≠ajまたは bi≠bj(1≦i<j≦M)
- −10 ** 9≦ci≦10 ** 9(1≦i≦M)
- ciは整数である。
- 与えられるグラフには、頂点 1から頂点 N への経路が存在する。

検討:
- 閉路が存在する場合、スコアをいくらでも大きくできる可能性がある
- 閉路を1周することで得られるスコア合計の符合によってinfにできるかどうかが判定可能
  - 符合が正: inf
  - 符合が0以下: 最短でNに到達したときのスコアが解
- 閉路が複数ある場合はどうするか
  - 1周したときに得られるスコア合計の符合が正かどうかで判断

必要な処理:
- 最短経路探索: ダイクストラ法? -> ベルマンフォード法（コストに正負があるため）
- 閉路を見つけ出す
- 閉路を1周したときのスコア合計

計算時間:
- ベルマンフォード法の時間計算量はO(NM)
- 解説通りにpythonで実装したらTLE判定...(約2100ms)
- 制約通りでいけば、NM = 1000 * 2000 = 2 * 10 ** 6
- 20msの化け物がいる...
"""

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append([a-1, b-1, -c])

inf = 10 ** 18
dist = [inf for _ in range(n)]
dist[0] = 0

for i in range(n-1):
    for a, b, c in edges:
        dist[b] = min(dist[b], dist[a] + c)
ans = -dist[n-1]

for i in range(n):
    for a, b, c in edges:
        if dist[a] + c < dist[b]:
            dist[b] = inf

if inf == dist[n-1]:
    print("inf")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
INF = float('inf')
e = []
for i in range(m):
    a, b, c = map(int, input().split())
    e.append((a - 1, b - 1, -c))
d = [0] * n
for i in range(n):
    flg = False
    for j in range(m):
        a, b, c = e[j]
        if d[a] != INF and d[b] > d[a] + c:
            d[b] = d[a] + c
            flg = True
    if i == n - 1:
        print('inf')
        exit(0)
    if not flg:
        break
d = [INF] * n
d[0] = 0
for i in range(n):
    flg = False
    for j in range(m):
        a, b, c = e[j]
        if d[a] != INF and d[b] > d[a] + c:
            d[b] = d[a] + c
            flg = True
    if not flg:
        break
print(-d[n - 1])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
INF = float('inf')
e = []
for i in range(m):
    a, b, c = map(int, input().split())
    e.append((a - 1, b - 1, -c))
d = [INF] * n
d[0] = 0
for i in range(n):
    flg = False
    for j in range(m):
        a, b, c = e[j]
        if d[a] != INF and d[b] > d[a] + c:
            d[b] = d[a] + c
            flg = True
    if i == n - 1:
        print('inf')
        exit(0)
    if not flg:
        break
print(-d[n - 1])

Submission status: Wrong Answer

Solution code:
inf=1e13

def bellmanford(E,N):
    score=[inf for i in range(N)]
    score[0]=0
    loop=False
    for i in range(N):
        for edge in E:
            u=edge[0]
            v=edge[1]
            if u!=inf:
                score[v]=min(score[v],score[u]+edge[2])

    for edge in E:
        u = edge[0]
        v = edge[1]
        if score[u]+edge[2]<score[v]:
            loop=True
    return score,loop


if __name__ == '__main__':
    N,M=list(map(int, input().split()))
    graph={i:[] for i in range(N)}
    E=[list(map(int, input().split())) for _ in range(M)]
    E_2=[]
    negative_E=[]
    for a,b,c in E:
        graph[a-1].append((b-1,c))
        E_2.append((a-1,b-1,c))
        negative_E.append((a-1,b-1,-c))

    score,loop=bellmanford(negative_E,N)
    if loop:
        print("inf")
    else:
        print(-score[N-1])

Submission status: Wrong Answer

Solution code:
#ABC061D - Score Attack
#https://atcoder.jp/contests/abc061/tasks/abc061_d
#部分的WA
import sys
N, M = map(int, input().split())
p = [[] for i in range(N)]
for _ in range(M):
    a, b, c = list(map(int,input().split()))
    p[a-1].append((b-1,-c))

d = [float('Inf')]*N
d[0] = 0

for i in range(N-1):
    for t, w in p[i]:
        if d[i] + w < d[t]:
            d[t] = d[i] + w
            
for i in range(N):
    for t,w in p[i]:
        if d[i] + w < d[t]:
            print('inf')
            sys.exit()
            
            
            
print(-d[N-1])

Submission status: Wrong Answer

Solution code:
inf=1e13

def bellmanford(E,N):
    score=[inf for i in range(N)]
    score[0]=0
    loop=False
    for i in range(N):
        for edge in E:
            u=edge[0]
            v=edge[1]
            if u!=inf:
                score[v]=min(score[v],score[u]+edge[2])

    for edge in E:
        u = edge[0]
        v = edge[1]
        if score[u]+edge[2]<score[v] and (u==N-1 or v==N-1):
            loop=True
    return score,loop


if __name__ == '__main__':
    N,M=list(map(int, input().split()))
    graph={i:[] for i in range(N)}
    E=[list(map(int, input().split())) for _ in range(M)]
    E_2=[]
    negative_E=[]
    for a,b,c in E:
        graph[a-1].append((b-1,c))
        E_2.append((a-1,b-1,c))
        negative_E.append((a-1,b-1,-c))

    score,loop=bellmanford(negative_E,N)
    if loop:
        print("inf")
    else:
        print(-score[N-1])

Submission status: Wrong Answer

Solution code:
import sys
N, M = map(int, input().split())
p = [[] for i in range(N)]
for _ in range(M):
    a, b, c = list(map(int,input().split()))
    p[a-1].append((b-1,-c))

d = [float('Inf')]*N
d[0] = 0

for i in range(N):
    for t, w in p[i]:
        if d[i] + w < d[t]:
            d[t] = d[i] + w
            
for i in range(N):
    for t,w in p[i]:
        if d[i] + w < d[t]:
            print('inf')
            sys.exit()
            
            
            
print(-d[N-1])

Submission status: Wrong Answer

Solution code:

def bellmanford(E,N):
    score=[-1e12 for i in range(N)]
    score[0]=0
    loop=False
    for i in range(N):
        temp_E=[(e[0],e[1],e[2]) for e in E if e[0]<=i and e[1]<=i]
        for edge in temp_E:
            u=edge[0]
            v=edge[1]
            score[v]=max(score[v],score[u]+edge[2])
    for edge in E:
        u = edge[0]
        v = edge[1]
        if score[u]+edge[2]>score[v] and (u==N-1 or v==N-1):
            loop=True
    return score,loop


if __name__ == '__main__':
    N,M=list(map(int, input().split()))
    graph={i:[] for i in range(N)}
    E=[list(map(int, input().split())) for _ in range(M)]
    E_2=[]
    negative_E=[]
    for a,b,c in E:
        graph[a-1].append((b-1,c))
        E_2.append((a-1,b-1,c))
        negative_E.append((a-1,b-1,-c))

    score,loop=bellmanford(E_2,N)
    if loop:
        print("inf")
    else:
        print(score[N-1])

Submission status: Wrong Answer

Solution code:

def bellmanford(E,N):
    score=[-1e12 for i in range(N)]
    score[0]=0
    loop=False
    for i in range(N):
        temp_E=[(e[0],e[1],e[2]) for e in E if e[0]<=i and e[1]<=i]
        for edge in temp_E:
            u=edge[0]
            v=edge[1]
            score[v]=max(score[v],score[u]+edge[2])
    for edge in E:
        u = edge[0]
        v = edge[1]
        if score[u]+edge[2]>score[v]:
            loop=True
    return score,loop


if __name__ == '__main__':
    N,M=list(map(int, input().split()))
    graph={i:[] for i in range(N)}
    E=[list(map(int, input().split())) for _ in range(M)]
    E_2=[]
    negative_E=[]
    for a,b,c in E:
        graph[a-1].append((b-1,c))
        E_2.append((a-1,b-1,c))
        negative_E.append((a-1,b-1,-c))

    score,loop=bellmanford(E_2,N)
    print(score[N-1])

Submission status: Wrong Answer

Solution code:

def bellmanford(E,N):
    score=[-1e12 for i in range(N)]
    score[0]=0
    loop=False
    for i in range(N):
        temp_E=[(e[0],e[1],e[2]) for e in E if e[0]<=i and e[1]<=i]
        for edge in temp_E:
            u=edge[0]
            v=edge[1]
            score[v]=max(score[v],score[u]+edge[2])
    for edge in E:
        u = edge[0]
        v = edge[1]
        if score[u]+edge[2]>score[v]:
            loop=True
    return score,loop


if __name__ == '__main__':
    N,M=list(map(int, input().split()))
    graph={i:[] for i in range(N)}
    E=[list(map(int, input().split())) for _ in range(M)]
    E_2=[]
    negative_E=[]
    for a,b,c in E:
        graph[a-1].append((b-1,c))
        E_2.append((a-1,b-1,c))
        negative_E.append((a-1,b-1,-c))

    score,loop=bellmanford(E_2,N)
    if loop:
        print("inf")
    else:
        print(score[N-1])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
abc = [input() for _ in range(m)]

INF = [float('inf')]
def shortest_path(s,v,es):
  ''' s -> i の最短距離
    s:始点, v:頂点, es[i]: [辺の始点,辺の終点,コスト]
  '''
  d = INF * n
  d[s] = 0
  
  while True:
    update = False
    
    for ef,et,ec in es:
      if d[ef] != INF and d[et] > d[ef] + ec:
        d[et] = d[ef] + ec
        update = True
    
    if not update:
      break
  
  return d        


#True : 負の閉路が存在する
def find_negative_loop(n,w,es):
  d = INF * n
  d[0] = 0    # この始点はどこでもよい
  for i in range(n):
    for j in range(w):           
      ef,et,ec = es[j]      
      if d[et] > d[ef] + ec:
        d[et] = d[ef] + ec
        if i == n-1:
          return True
  return False


es = []

for li in map(str.split,abc):  
  x,y,z = map(int,li)
  es.append([x-1,y-1,-z])  

if find_negative_loop(n,m,es):
  print('inf')
else:
  d = shortest_path(0,n,es)
  print(-d[-1])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())

V = n
from collections import defaultdict
G = [[] for i in range(V)]
for _ in range(m):
   a,b,c = map(int,input().split())
   G[a-1].append((b-1, -c))
# V: グラフの頂点数
# r: 始点
# G[v] = [(w, cost), ...]: 頂点vからコストcostで到達できる頂点w
INF = 10**18
dist = [INF] * V
dist[0] = 0
update = 1
for x in range(4*V):
    update = 0
    for v, e in enumerate(G):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                if x > 2*V:
                    dist[v] = float("inf")
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break

if dist[-1] == float("inf"):
    print('inf')
else:
    print(-dist[-1])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())

V = n
from collections import defaultdict
G = [[] for i in range(V)]
for _ in range(m):
   a,b,c = map(int,input().split())
   G[a-1].append((b-1, -c))
# V: グラフの頂点数
# r: 始点
# G[v] = [(w, cost), ...]: 頂点vからコストcostで到達できる頂点w
INF = 10**18
dist = [INF] * V
dist[0] = 0
update = 1
for x in range(3*V):
    update = 0
    for v, e in enumerate(G):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                if x > V:
                    dist[v] = float("inf")
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break

if dist[-1] == float("inf"):
    print('inf')
else:
    print(-dist[-1])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())

V = n
from collections import defaultdict
G = [[] for i in range(V)]
for _ in range(m):
   a,b,c = map(int,input().split())
   G[a-1].append((b-1, -c))
# V: グラフの頂点数
# r: 始点
# G[v] = [(w, cost), ...]: 頂点vからコストcostで到達できる頂点w
INF = 10**18
dist = [INF] * V
dist[0] = 0
update = 1
for x in range(2*V):
    update = 0
    for v, e in enumerate(G):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                if x > V:
                    dist[v] = float("inf")
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break

if dist[-1] == float("inf"):
    print('inf')
else:
    print(-dist[-1])

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np 
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m = I[:2]
a, b, c = I[2:].reshape(-1, 3).T
a -= 1; b -= 1
c = np.negative(c)
graph = np.zeros((n, n))
graph[a, b] = c

def main():
    try:
        dist = bellman_ford(csgraph=csr_matrix(graph), directed=True, indices=0)
        return int(-dist[n-1])
    except:
        return 'inf'

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def BellmanFord(graph,num_v,source=0):
    #グラフの初期化
    edges=[]
    for u in range(num_v):
        for v,d in graph[u]:
            edges.append((u,v,d))
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source]=0
    neg=[False for i in range(num_v)]
    neg_flg=False
    
    #辺の緩和
    for i in range(num_v*2):
        for u,v,d in edges:
            if dist[v] > dist[u] + d:
                dist[v] = dist[u] + d
                if i>=num_v-1:# and neg[v]==True:
                    neg_flg=True
                    return neg_flg,dist
                neg[v] = True
    return neg_flg,dist
 

show_flg=False
show_flg=True

n,m=LI()
g=[[] for i in range(n)]

for i in range(m):
    a,b,c=LI_()
    c=-c-1
    g[a].append((b,c))
    #g[b].append((a,c))
    #show((a,b,-c))

fl,d=BellmanFord(g,n,0)
if fl:
    ans='inf'
else:
    ans=-d[n-1]
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def BellmanFord(graph,num_v,source=0):
    #グラフの初期化
    edges=[]
    for u in range(num_v):
        for v,d in graph[u]:
            edges.append((u,v,d))
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source]=0
    neg=[False for i in range(num_v)]
    neg_flg=False
    
    #辺の緩和
    for i in range(num_v*2):
        for u,v,d in edges:
            if dist[v] > dist[u] + d:
                dist[v] = dist[u] + d
                if i==num_v-1:# and neg[v]==True:
                    neg_flg=True
                    return neg_flg,dist
                neg[v] = True
    return neg_flg,dist
 

show_flg=False
show_flg=True

n,m=LI()
g=[[] for i in range(n)]

for i in range(m):
    a,b,c=LI_()
    c=-c-1
    g[a].append((b,c))
    #g[b].append((a,c))
    #show((a,b,-c))

fl,d=BellmanFord(g,n,0)
if fl:
    ans='inf'
else:
    ans=-d[n-1]
print(ans)