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:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    c = []
    d = [1e10]*N
    
    for i in range(M):
        s1, s2, s3 = (int(_) for _ in input().split())
        a.append(s1)
        b.append(s2)
        c.append(-s3)
    d[0] = 0
    cnt = [0]*N
    for j in range(N):
        update=False
        for i in range(M):
            if(d[a[i]-1] == 1e10):
                continue
            if(d[b[i]-1] > d[a[i]-1]+c[i]):
                d[b[i]-1] = d[a[i]-1]+c[i]
                cnt[b[i]-1]+=1
                update=True
        if not update:
            break
    if cnt[N-1] < N:
        ans = -d[N-1]
    else:
        ans = 'inf'
    
    # negative = [False]*N
    # for j in range(N):
    #     for i in range(M):
    #         if(d[a[i]-1] == 1e10):
    #             continue
    #         if(d[b[i]-1] > d[a[i]-1]+c[i]):
    #             d[b[i]-1] = d[a[i]-1]+c[i]
    #             negative[b[i]-1] = True
    #         if(negative[a[i]-1]):
    #             negative[b[i]-1] = True
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    c = []
    d = [1e10]*N
    
    for i in range(M):
        s1, s2, s3 = (int(_) for _ in input().split())
        a.append(s1)
        b.append(s2)
        c.append(-s3)
    d[0] = 0
    cnt = [0]*N
    for j in range(N):
        update=False
        for i in range(M):
            if(d[a[i]-1] == 1e10):
                continue
            if(d[b[i]-1] > d[a[i]-1]+c[i]):
                d[b[i]-1] = d[a[i]-1]+c[i]
                cnt[b[i]-1]+=1
                update=True
            if not update:
                break
    if cnt[N-1] < N:
        ans = -d[N-1]
    else:
        ans = 'inf'
    
    # negative = [False]*N
    # for j in range(N):
    #     for i in range(M):
    #         if(d[a[i]-1] == 1e10):
    #             continue
    #         if(d[b[i]-1] > d[a[i]-1]+c[i]):
    #             d[b[i]-1] = d[a[i]-1]+c[i]
    #             negative[b[i]-1] = True
    #         if(negative[a[i]-1]):
    #             negative[b[i]-1] = True
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    c = []
    d = [1e10]*N
    
    for i in range(M):
        s1, s2, s3 = (int(_) for _ in input().split())
        a.append(s1)
        b.append(s2)
        c.append(-s3)
    d[0] = 0

    for j in range(N):
        for i in range(M):
            if(d[a[i]-1] == 1e10):
                continue
            if(d[b[i]-1] > d[a[i]-1]+c[i]):
                d[b[i]-1] = d[a[i]-1]+c[i]
    ans = d[N-1]
    
    negative = [False]*N
    for j in range(N):
        for i in range(M):
            if(d[a[i]-1] == 1e10):
                continue
            if(d[b[i]-1] > d[a[i]-1]+c[i]):
                d[b[i]-1] = d[a[i]-1]+c[i]
                negative[b[i]-1] = True
            if(negative[a[i]-1]):
                negative[b[i]-1] = True
    if negative[N-1]:
        print('inf')
    else:
        print(-ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    c = []
    d = []
    for i in range(N):
        d.append(list(-1e10 for _ in range(N)))
    for i in range(M):
        s1, s2, s3 = (int(_) for _ in input().split())
        a.append(s1)
        b.append(s2)
        c.append(s3)
        
    for i in range(M):
        d[a[i]-1][b[i]-1] = c[i]

    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = max(d[i][j],d[i][k]+d[k][j])
    if d[N-1][0] != -1e10:
        ans = 'inf'
    else:
        ans = d[0][N-1]
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
V, E = map(int, input().split())

es = []
for i in range(E):
    a, b, c = map(int, input().split())
    es.append([a - 1, b - 1, - c])

d = [0] * V
INF = float('inf')

def shortest_path(s):
    for i in range(V):
        d[i] = INF
    d[s] = 0
    while True:
        update = 0
        for i in range(E):
            e = es[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = 1
        if update == 0:
            break

def find_negative_loop():
    d = [0] * V
    for i in range(V):
        for j in range(E):
            e = es[j]
            if d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                
                if i == V -1:
                    return True
    return False

if find_negative_loop():
    print('inf')
else:
    shortest_path(0)
    print(- d[V - 1])

Submission status: Wrong Answer

Solution code:
#コストをマイナスにして最小化する
import sys
inf=10**15
fastinput=sys.stdin.readline
N,M=map(int,fastinput().split())
cost=[inf]*N
cost[0]=0
abc=[[int(o) for o in fastinput().split()] for _ in range(M)]#[a,b,c];点a-1とb-1を結ぶ辺のコストが-c
for t in range(N):
    changed=0
    for a,b,c in abc:
        if cost[b-1]>cost[a-1]-c:
            changed=1#コストの更新あり
            cost[b-1]=cost[a-1]-c
if changed==1:
    print("inf")
else:
    print(-cost[N-1])

Submission status: Wrong Answer

Solution code:
import sys

def bellman_ford(n, edges, source):
    """Bellman Ford algorithm

    n: int, the number of nodes.
    edges: list, [edge1, edge2, ... ]
           edge_i = [node, neighbour, weight of the edge]
    source: int, start node.
    """
    # Initializing the distance from source.
    inf = float('inf')
    dist=[inf for i in range(n)]
    dist[source] = 0

    # Relaxation step
    for i in range(n):
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i == n - 1:
                    return -1

    return dist


def main():
    input = sys.stdin.readline
    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))

    dist = bellman_ford(N, edges, 0)

    if dist == -1:
        return 'inf'
    else:
        return int(-dist[N-1])


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

Submission status: Wrong Answer

Solution code:
import sys

def bellman_ford(n, edges, source):
    """Bellman Ford algorithm

    n: int, the number of nodes.
    edges: list, [edge1, edge2, ... ]
           edge_i = [node, neighbour, weight of the edge]
    source: int, start node.
    """
    # Initializing the distance from source.
    inf = float('inf')
    dist=[inf for i in range(n)]
    dist[source] = 0

    # Relaxation step
    for i in range(1, n):
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i == n - 1:
                    return -1

    return dist


def main():
    input = sys.stdin.readline
    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))

    dist = bellman_ford(N, edges, 0)

    if dist == -1:
        return 'inf'
    else:
        return -dist[N-1]


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

Submission status: Wrong Answer

Solution code:
import sys

def bellman_ford(n, edges, source):
    """Bellman Ford algorithm

    n: int, the number of nodes.
    edges: list, [edge1, edge2, ... ]
           edge_i = [node, neighbour, weight of the edge]
    source: int, start node.
    """
    # Initializing the distance from source.
    inf = float('inf')
    dist=[-inf for i in range(n)]
    dist[source] = 0

    # Relaxation step
    for i in range(n):
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i == n - 1:
                    return -1

    return dist


def main():
    input = sys.stdin.readline
    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))

    dist = bellman_ford(N, edges, 0)

    if dist == -1:
        return 'inf'
    else:
        return dist[N-1]


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

Submission status: Wrong Answer

Solution code:
import sys

def bellman_ford(n, edges, source):
    """Bellman Ford algorithm

    n: int, the number of nodes.
    edges: list, [edge1, edge2, ... ]
           edge_i = [node, neighbour, weight of the edge]
    source: int, start node.
    """
    # Initializing the distance from source.
    inf = float('inf')
    dist=[inf for i in range(n)]
    dist[source] = 0

    # Relaxation step
    for i in range(n):
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i == n - 1:
                    return -1

    return dist


def main():
    input = sys.stdin.readline
    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))

    dist = bellman_ford(N, edges, 0)

    if dist == -1:
        return 'inf'
    else:
        return dist[N-1]


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

Submission status: Wrong Answer

Solution code:
import sys

def bellman_ford(n, edges, source):
    """Bellman Ford algorithm

    n: int, the number of nodes.
    edges: list, [edge1, edge2, ... ]
           edge_i = [node, neighbour, weight of the edge]
    source: int, start node.
    """
    # Initializing the distance from source.
    inf = float('inf')
    dist=[inf for i in range(n)]
    dist[source] = 0

    # Relaxation step
    for i in range(n):
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i == n - 1:
                    return -1

    return dist


def main():
    input = sys.stdin.readline
    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))

    dist = bellman_ford(N, edges, 0)

    if dist == -1:
        return 'inf'
    else:
        return -dist[N-1]


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

Submission status: Wrong Answer

Solution code:
inf=float('inf')
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0]-1, ai[1]-1, -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
for i in range(n+1):
    flag=False
    for abci in abc:
        if d[abci[1]]>d[abci[0]]+abci[2]:
            flag=True
            d[abci[1]]=d[abci[0]]+abci[2]
            if i==n:
                print('inf')
                exit()

print(-d[n-1])

Submission status: Wrong Answer

Solution code:
inf=float('inf')
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0]-1, ai[1]-1, -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
for i in range(n):
    flag=False
    for abci in abc:
        if d[abci[1]]>d[abci[0]]+abci[2]:
            flag=True
            d[abci[1]]=d[abci[0]]+abci[2]
            if i==n-1:
                print('inf')
                exit()

print(-d[n-1])

Submission status: Wrong Answer

Solution code:
inf=float('inf')
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0]-1, ai[1]-1, -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
for i in range(n):
    flag=False
    for abci in abc:
        if d[abci[1]]>d[abci[0]]+abci[2]:
            flag=True
            d[abci[1]]=d[abci[0]]+abci[2]
    if i==n-1:
        ans='inf'
        break
    if not flag:
        ans=-d[n-1]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
inf=float('inf')
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0]-1, ai[1]-1, -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
cnt=0
while True:
    cnt+=1
    flag=False
    if cnt==n+100:
        ans='inf'
        break
    for abci in abc:
        if d[abci[1]]>d[abci[0]]+abci[2]:
            flag=True
            d[abci[1]]=d[abci[0]]+abci[2]
    if not flag:
        ans=-d[n-1]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
inf=10**15
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0], ai[1], -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
cnt=0
while True:
    cnt+=1
    flag=False
    if cnt==n+100:
        ans='inf'
        break
    for abci in abc:
        if d[abci[0]-1]<inf and d[abci[1]-1]>d[abci[0]-1]+abci[2]:
            flag=True
            d[abci[1]-1]=d[abci[0]-1]+abci[2]
    if not flag:
        ans=-d[n-1]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
inf=10**13
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0], ai[1], -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
cnt=0
while True:
    cnt+=1
    flag=False
    if cnt==n+100:
        ans='inf'
        break
    for abci in abc:
        if d[abci[0]-1]<inf and d[abci[1]-1]>d[abci[0]-1]+abci[2]:
            flag=True
            d[abci[1]-1]=d[abci[0]-1]+abci[2]
    if not flag:
        ans=-d[n-1]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
inf=10**8
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0], ai[1], -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
cnt=0
while True:
    cnt+=1
    flag=False
    if cnt==n+1:
        ans='inf'
        break
    for abci in abc:
        if d[abci[0]-1]<inf and d[abci[1]-1]>d[abci[0]-1]+abci[2]:
            flag=True
            d[abci[1]-1]=d[abci[0]-1]+abci[2]
    if not flag:
        ans=-d[n-1]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
inf=10**8
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0], ai[1], -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
cnt=0
while True:
    cnt+=1
    flag=False
    if cnt==n:
        ans='inf'
        break
    for abci in abc:
        if d[abci[0]-1]<inf and d[abci[1]-1]>d[abci[0]-1]+abci[2]:
            flag=True
            d[abci[1]-1]=d[abci[0]-1]+abci[2]
    if not flag:
        ans=-d[n-1]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
def bellman_ford(vertex_num: int, edges: list, source: int) -> list:
    distances = [float('inf')] * (vertex_num)
    distances[source] = 0

    for _ in range(vertex_num-1):
        for u, v, c in edges:
            distances[v] = min(distances[v], distances[u] + c)

    for u, v, c in edges:
        if distances[u] + c < distances[v] and v == vertex_num-1:
            return []

    return distances


def score_attack(N: int, M: int, edges: list) -> int:
    distances = bellman_ford(N, [(u-1, v-1, -c) for u, v, c in edges], 0)

    return -distances[N - 1] if distances else float('inf')


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(M)]
    ans = score_attack(N, M, edges)
    print(ans)

Submission status: Wrong Answer

Solution code:
def bellman_ford(vertex_num: int, edges: list, source: int) -> list:
    distances = [float('inf')] * (vertex_num)
    distances[source] = 0

    for _ in range(1, vertex_num):
        for u, v, c in edges:
            distances[v] = min(distances[v], distances[u] + c)

    for u, v, c in edges:
        if distances[u] + c < distances[v]:
            return []

    return distances


def score_attack(N: int, M: int, edges: list) -> int:
    distances = bellman_ford(N, [(u-1, v-1, -c) for u, v, c in edges], 0)

    return -distances[N - 1] if distances else float('inf')


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(M)]
    ans = score_attack(N, M, edges)
    print(ans)

Submission status: Wrong Answer

Solution code:
def bellman_ford(vertex_num: int, edges: list, source: int) -> list:
    distances = [float('inf')] * (vertex_num)
    distances[source] = 0

    for _ in range(vertex_num):
        for u, v, c in edges:
            distances[v] = min(distances[v], distances[u] + c)

    for u, v, c in edges:
        if distances[u] + c < distances[v]:
            return []

    return distances


def score_attack(N: int, M: int, edges: list) -> int:
    distances = bellman_ford(N, [(u-1, v-1, -c) for u, v, c in edges], 0)

    return -distances[N - 1] if distances else float('inf')


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(M)]
    ans = score_attack(N, M, edges)
    print(ans)

Submission status: Wrong Answer

Solution code:
def bellman_ford(vertex_num: int, edges: list, source: int) -> list:
    distances = [float('inf')] * (vertex_num)
    distances[source] = 0

    for _ in range(vertex_num):
        for u, v, c in edges:
            distances[v] = min(distances[v], distances[u] + c)

    for u, v, c in edges:
        if distances[u] + c < distances[v]:
            return []

    return distances


def score_attack(N: int, M: int, edges: list) -> int:
    distances = bellman_ford(N, [(u-1, v-1, -c) for u, v, c in edges], 0)

    return -distances[N - 1] if distances else float('inf')


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(M)]
    ans = score_attack(N, M, edges)
    print('inf' if ans == float('inf') else str(ans))

Submission status: Wrong Answer

Solution code:
inf = float('inf')

# distの初期化: dist = [inf for _ in range(N)]; dist[start] = 0
# True - >正常に更新, False -> 負閉路有り
def bellmanford(dist,edges,N):
    for i in range(N):
        for v ,nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                # 頂点数Nなら更新は高々N-1回で済む
                # N回目に更新を行うなら負閉路があるということ
                if i == N-1:
                    return False
    return True

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

flag = bellmanford(dist,info,N)
ans = -dist[N-1] if flag is True else "inf"
print(ans)

Submission status: Wrong Answer

Solution code:
inf = float('inf')

N,M = map(int,input().split())
info = []
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1; b -= 1
    info.append((a,b,c))
 
dist = [-inf for _ in range(N)]
dist[0] = 0
for i in range(N):
    for v,nv,w in info:
        if dist[nv] < dist[v] + w:
            dist[nv] = dist[v] + w
            if i == N-1:
                print("inf")
                exit()
ans = dist[N-1]
print(ans)

Submission status: Wrong Answer

Solution code:
inf = float('inf')

def bellmanford(dist,edges,n):
    for i in range(n):
        for v,nv,w in edges:
            if dist[nv] < dist[v] + w:
                dist[nv] = dist[v] + w
                if i == n-1:
                    return False
    return True

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

flag = bellmanford(dist,edges,N)
ans = dist[N-1] if flag is True else "inf"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

class WeightedUnionfind:

    __slots__ = ['nodes','diff_weight']

    def __init__(self, n):
        self.nodes = [-1]*n
        self.diff_weight = [0]*n

    def root(self, x):
        if self.nodes[x] < 0:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.diff_weight[x] += self.diff_weight[self.nodes[x]]
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y, w=0):
        w += self.weight(x); w -= self.weight(y)
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        size_x = -self.nodes[x]; size_y = -self.nodes[y]
        if size_x < size_y:
            x, y = y, x; w = -w
        self.nodes[x] += self.nodes[y]
        self.nodes[y] = x
        self.diff_weight[y] = w

    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]

    def diff(self, x, y):
        return self.weight(y) - self.weight(x)

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.nodes[self.root(x)]

N,M = map(int,input().split())
info = []
ad = [deque() for _ in range(N)]
num = [0]*N

for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1; b -= 1
    ad[a].append(b)
    num[b] += 1
    info.append((a,b,c))

L = []
S = deque()

for v in range(N):
    if num[v] == 0:
        S.append(v)

while S:
    v = S.popleft()
    L.append(v)
    for _ in range(len(ad[v])):
        nv = ad[v].popleft()
        num[nv] -= 1
        if num[nv] == 0:
            S.append(nv)

for edge in ad:
    if edge:
        print("inf")
        exit()

wuf = WeightedUnionfind(N)
for a,b,c in info:
    if wuf.same(a,b):
        if wuf.diff(a,b) < c:
            wuf.diff_weight[b] = wuf.diff_weight[a] + c
    else:
        wuf.unite(a,b,c)
ans = wuf.diff(0,N-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

class WeightedUnionfind:

    __slots__ = ['nodes','diff_weight']

    def __init__(self, n):
        self.nodes = [-1]*n
        self.diff_weight = [0]*n

    def root(self, x):
        if self.nodes[x] < 0:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.diff_weight[x] += self.diff_weight[self.nodes[x]]
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y, w=0):
        w += self.weight(x); w -= self.weight(y)
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        size_x = -self.nodes[x]; size_y = -self.nodes[y]
        if size_x < size_y:
            x, y = y, x; w = -w
        self.nodes[x] += self.nodes[y]
        self.nodes[y] = x
        self.diff_weight[y] = w

    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]

    def diff(self, x, y):
        return self.weight(y) - self.weight(x)

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.nodes[self.root(x)]

N,M = map(int,input().split())
info = []
ad = [deque() for _ in range(N)]
num = [0]*N

for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1; b -= 1
    ad[a].append(b)
    num[b] += 1
    info.append((a,b,c))

L = []
S = deque()

for v in range(N):
    if num[v] == 0:
        S.append(v)

while S:
    v = S.popleft()
    L.append(v)
    for _ in range(len(ad[v])):
        nv = ad[v].popleft()
        num[nv] -= 1
        if num[nv] == 0:
            S.append(nv)

for dq in ad:
    if dq:
        print("inf")
        exit()

wuf = WeightedUnionfind(N)
for a,b,c in info:
    if wuf.same(a,b) and wuf.diff(a,b) > c:
        pass
    else:
        wuf.unite(a,b,c)
ans = wuf.diff(0,N-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

class WeightedUnionfind:

    __slots__ = ['nodes','diff_weight']

    def __init__(self, n):
        self.nodes = [-1]*n
        self.diff_weight = [0]*n

    def root(self, x):
        if self.nodes[x] < 0:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.diff_weight[x] += self.diff_weight[self.nodes[x]]
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y, w=0):
        w += self.weight(x); w -= self.weight(y)
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        size_x = -self.nodes[x]; size_y = -self.nodes[y]
        if size_x < size_y:
            x, y = y, x; w = -w
        self.nodes[x] += self.nodes[y]
        self.nodes[y] = x
        self.diff_weight[y] = w

    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]

    def diff(self, x, y):
        return self.weight(y) - self.weight(x)

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.nodes[self.root(x)]

N,M = map(int,input().split())
info = []
ad = [deque() for _ in range(N)]
num = [0]*N

for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1; b -= 1
    ad[a].append(b)
    num[b] += 1
    info.append((a,b,c))

L = []
S = deque()

for v in range(N):
    if num[v] == 0:
        S.append(v)

if not S:
    print("inf")
    exit()

while S:
    v = S.popleft()
    L.append(v)
    for _ in range(len(ad[v])):
        nv = ad[v].popleft()
        num[nv] -= 1
        if num[nv] == 0:
            S.append(nv)

for dq in ad:
    if not ad:
        print("inf")
        exit()

wuf = WeightedUnionfind(N)
for a,b,c in info:
    if wuf.same(a,b) and wuf.diff(a,b) > c:
        pass
    else:
        wuf.unite(a,b,c)
ans = wuf.diff(0,N-1)
print(ans)