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:
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)

if len(L) != N:
    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)

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)

if L == []:
    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:
INF = float('inf')

def solve():
    lp = [-INF] * n
    lp[0] = 0

    for i in range(n):
        for a, b, c in es:
            if lp[a] != -INF and lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                if i == n - 1:
                    return 'inf'
    return lp[n - 1]


if __name__ == '__main__':
    n, m = map(int, input().split())
    es = []

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

    print(solve())

Submission status: Wrong Answer

Solution code:
INF = 1000000000000000000

def solve():
    lp = [-INF] * n
    lp[0] = 0

    for i in range(n):
        for a, b, c in es:
            if lp[a] > -INF and lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                if i == n - 1:
                    return 'inf'
    return lp[n - 1]


if __name__ == '__main__':
    n, m = map(int, input().split())
    es = []

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

    print(solve())

Submission status: Wrong Answer

Solution code:
INF = 10000000000000000

def solve():
    lp = [0] * n

    flag = True
    i = 1
    while flag and i < n:
        flag = False
        for a, b, c in es:
            if lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                flag = True
        i += 1
    if flag:
        return 'inf'

    lp = [-INF] * n
    lp[0] = 0

    flag = True
    while flag:
        flag = False
        for a, b, c in es:
            if lp[a] != -INF and lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                flag = True
    return lp[n - 1]



if __name__ == '__main__':
    n, m = map(int, input().split())
    es = []

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

    print(solve())

Submission status: Wrong Answer

Solution code:
INF = 10000000000000000

def solve():
    lp = [0] * n

    flag = True
    i = 0
    while flag and i < n:
        flag = False
        for a, b, c in es:
            if lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                flag = True
        i += 1
    if flag:
        return 'inf'

    lp = [-INF] * n
    lp[0] = 0

    flag = True
    while flag:
        flag = False
        for a, b, c in es:
            if lp[a] != -INF and lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                flag = True
    return lp[n - 1]



if __name__ == '__main__':
    n, m = map(int, input().split())
    es = []

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

    print(solve())

Submission status: Wrong Answer

Solution code:
INF = 10000000000000000

def solve():
    lp = [-INF] * n
    lp[0] = 0

    for i in range(n):
        for a, b, c in es:
            if lp[a] != -INF and lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                if i == n - 1:
                    return 'inf'
    return lp[n - 1]


if __name__ == '__main__':
    n, m = map(int, input().split())
    es = []

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

    print(solve())

Submission status: Wrong Answer

Solution code:
INF = 1000000000000000000

def solve():
    lp = [-INF] * n
    lp[0] = 0

    for i in range(n):
        for a, b, c in es:
            if lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                if i == n - 1:
                    return 'inf'
    return lp[n - 1]


if __name__ == '__main__':
    n, m = map(int, input().split())
    es = []

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

    print(solve())

Submission status: Wrong Answer

Solution code:
INF = 10000000000000000

def solve():
    lp = [-INF] * n
    lp[0] = 0

    for i in range(n):
        for a, b, c in es:
            if lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                if i == n - 1:
                    return 'inf'
    return lp[n - 1]


if __name__ == '__main__':
    n, m = map(int, input().split())
    es = []

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

    print(solve())

Submission status: Wrong Answer

Solution code:
INF = 10000000000000000

def solve():
    lp = [INF] * n
    lp[0] = 0

    flag = True
    i = 1
    while flag and i < n:
        flag = False
        for a, b, c in es:
            if lp[b] > lp[a] + c:
                lp[b] = lp[a] + c
                flag = True
        i += 1
    if flag:
        return 'inf'
    return -lp[n - 1]


if __name__ == '__main__':
    n, m = map(int, input().split())
    es = []

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

    print(solve())

Submission status: Wrong Answer

Solution code:
INF = 10000000000000000

def solve():
    lp = [INF] * n
    lp[0] = 0

    flag = True
    i = 0
    while flag and i < n:
        flag = False
        for a, b, c in es:
            if lp[b] > lp[a] + c:
                lp[b] = lp[a] + c
                flag = True
        i += 1
    if flag:
        return 'inf'
    return -lp[n - 1]


if __name__ == '__main__':
    n, m = map(int, input().split())
    es = []

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

    print(solve())

Submission status: Wrong Answer

Solution code:
INF = 10000000000000000

def solve():
    lp = [0] * n

    flag = True
    i = 0
    while flag and i < n:
        flag = False
        for a, b, c in es:
            if lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                flag = True
        i += 1
    if flag:
        return 'inf'

    lp = [-INF] * n
    lp[0] = 0

    flag = True
    while flag:
        flag = False
        for a, b, c in es:
            if lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                flag = True
    return lp[n - 1]



if __name__ == '__main__':
    n, m = map(int, input().split())
    es = []

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

    print(solve())

Submission status: Wrong Answer

Solution code:
INF = 10000000000000000

def solve():
    lp = [-INF] * n
    lp[0] = 0

    flag = True
    i = 0
    while flag and i < n:
        flag = False
        for a, b, c in es:
            if lp[b] < lp[a] + c:
                lp[b] = lp[a] + c
                flag = True
        i += 1
    if flag:
        return 'inf'
    return lp[n - 1]


if __name__ == '__main__':
    n, m = map(int, input().split())
    es = []

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

    print(solve())

Submission status: Wrong Answer

Solution code:
#D問題
N,M=map(int,input().split())
ABC=[]
for i in range(M):
    a,b,c=map(int,input().split())
    ABC.append([a,b,-c])
negative=[]
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #負閉路の検出
    global negative
    negative=[False for i in range(num_v)]
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                negative[i]=True
                if i==num_v-1: return -1
    return dist
ans=BellmanFord(ABC,N,1)
if ans == -1 or negative[-1]:
    print("inf")
else:
    print(-ans[N-1])

Submission status: Wrong Answer

Solution code:
#D問題
N,M=map(int,input().split())
ABC=[]
for i in range(M):
    a,b,c=map(int,input().split())
    ABC.append([a,b,-c])
negative=[]
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #負閉路の検出
    global negative
    negative=[False for i in range(num_v)]
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                negative[i]=True
                if i==num_v-1: return -1
    return dist
ans=BellmanFord(ABC,N,1)
if ans == -1 or negative[-1]:
    print("inf")
else:
    print(-ans[-1])

Submission status: Wrong Answer

Solution code:
#D問題
N,M=map(int,input().split())
ABC=[]
for i in range(M):
    a,b,c=map(int,input().split())
    ABC.append([a,b,-c])
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i==num_v-1: return -1
    return dist
ans=BellmanFord(ABC,N,1)
if ans == -1:
    print("inf")
else:
    print(-ans[-1])

Submission status: Wrong Answer

Solution code:
#D問題
N,M=map(int,input().split())
ABC=[]
for i in range(M):
    a,b,c=map(int,input().split())
    ABC.append([a,b,-c])
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i==num_v-1: return -1
    return dist
ans=BellmanFord(ABC,N,1)
if ans == -1:
    print("inf")
else:
    print(-ans[-1])

Submission status: Wrong Answer

Solution code:
#D問題
N,M=map(int,input().split())
ABC=[]
for i in range(M):
    a,b,c=map(int,input().split())
    ABC.append([a,b,-c])
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i==num_v-1: return -1
    return dist
ans=BellmanFord(ABC,N,1)
if ans == -1:
    print("inf")
else:
    ansint=-min(ans)
    print(ansint)

Submission status: Wrong Answer

Solution code:
class edge:
    def __init__(self,from_,to,cost):
        self.from_=from_
        self.to=to
        self.cost=cost

def BellmanFord(edges,v):
    d=[float('inf') for _ in range(v)]
    d[0]=0
    while True:
        update=False
        for e in edges:
            if(d[e.from_]!=float('inf') and d[e.to] > d[e.from_]+e.cost):
                d[e.to]=d[e.from_]+e.cost
                update=True
        if(not update):
            break
    return d

def find_negative_loop(G,v):
    d=[0 for i in range(v)]
    for i in range(v):
        for e in G:
            if(d[e.to]>d[e.from_]+e.cost):
                d[e.to]=d[e.from_]+e.cost
                if(i==v-1):
                    return True

    return False

N,W=map(int,input().split())
G=[]
for i in range(W):
    a,b,c=map(int,input().split())
    G.append(edge(a-1,b-1,-1*c))

if(find_negative_loop(G,N)):
    print('inf')
else:
    print(BellmanFord(G,N)[-1]*-1)

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
G_ls = []
d = [-float("inf") for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(N):
    for j in range(M):
        is_updated = False
        a, b, c = G_ls[j]
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
G_ls = []
d = [-float("inf") for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(N):
    is_updated = False
    for j in range(M):
        a, b, c = G_ls[j]
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
G_ls = []
d = [-1e15 for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(N-1):
    is_updated = False
    for j in range(M):
        a, b, c = G_ls[j]
        if d[a] == -1e15:
            continue
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
    if not is_updated:
        break
_d = [0 for i in range(N)]
for i in range(N-1):
    is_updated = False
    for j in range(M):
        a, b, c = G_ls[j]
        if _d[a] == -1e15:
            continue
        _d[b], is_updated = update(_d[b], _d[a] + c, is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
G_ls = []
d = [-1e15 for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x <= y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(N):
    is_updated = False
    for j in range(M):
        a, b, c = G_ls[j]
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
G = [[None for j in range(N)] for i in range(N)]
G_ls = []
d = [-1e15 for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G[a][b] = c
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(N):
    is_updated = False
    for j in range(M):
        a, b, c = G_ls[j]
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
G = [[None for j in range(N)] for i in range(N)]
G_ls = []
d = [-1e15 for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G[a][b] = c
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(N):
    is_updated = False
    for j in range(M):
        a, b, c = G_ls[j]
        if d[a] is None:
            continue
        if d[b] is None:
            d[b] = d[a] + c
            is_updated = True
            continue
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
G = [[None for j in range(N)] for i in range(N)]
G_ls = []
d = [None for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G[a][b] = c
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(2*N):
    is_updated = False
    for j in range(M):
        a, b, c = G_ls[j]
        if d[a] is None:
            continue
        if d[b] is None:
            d[b] = d[a] + c
            is_updated = True
            continue
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
G = [[None for j in range(N)] for i in range(N)]
G_ls = []
d = [None for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G[a][b] = c
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(N+1):
    is_updated = False
    for j in range(M):
        a, b, c = G_ls[j]
        if d[a] is None:
            continue
        if d[b] is None:
            d[b] = d[a] + c
            is_updated = True
            continue
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
G = [[None for j in range(N)] for i in range(N)]
G_ls = []
d = [None for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G[a][b] = c
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(N):
    is_updated = False
    for j in range(M):
        a, b, c = G_ls[j]
        if d[a] is None:
            continue
        if d[b] is None:
            d[b] = d[a] + c
            is_updated = True
            continue
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
G = [[None for j in range(N)] for i in range(N)]
G_ls = []
d = [None for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G[a][b] = c
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated

d[G_ls[0][0]] = 0
for i in range(N):
    is_updated = False
    for j in range(M):
        a, b, c = G_ls[j]
        if d[a] is None:
            continue
        if d[b] is None:
            d[b] = d[a] + c
            is_updated = True
            continue
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
    if not is_updated:
        break
if is_updated:
    print("inf")
else:
    print(d[-1])

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [{} for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        adj[a][b] = c
    points = [-float("inf")] * (N+1)
    q = deque([(1, 0, {})])
    while len(q):
        cur, point, visited = q.popleft()
        points[cur] = max(points[cur], point)
        nvisited = {v: visited[v] for v in visited}
        nvisited[cur] = point
        for nxt in adj[cur]:
            npoint = point + adj[cur][nxt]
            if nxt in nvisited and nvisited[nxt] < npoint:
                print("inf")
                return
            if nxt in nvisited:
                continue
            q.append((nxt, npoint, nvisited))
    print(points[N])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [{} for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        adj[a][b] = c
    points = [-float("inf")] * (N+1)
    q = deque([(1, 0, {})])
    while len(q):
        cur, point, visited = q.popleft()
        points[cur] = point
        nvisited = {v: visited[v] for v in visited}
        nvisited[cur] = point
        for nxt in adj[cur]:
            npoint = point + adj[cur][nxt]
            if nxt in nvisited and nvisited[nxt] < npoint:
                print("inf")
                return
            q.append((nxt, npoint, nvisited))
    print(points[N])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [{} for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        adj[a][b] = c
    points = [-float("inf")] * (N+1)
    q = deque([(1, 0, {})])
    while len(q):
        cur, point, visited = q.popleft()
        if point <= points[cur]:
            continue
        points[cur] = point
        nvisited = {v: visited[v] for v in visited}
        nvisited[cur] = point
        for nxt in adj[cur]:
            npoint = point + adj[cur][nxt]
            if nxt in nvisited and nvisited[nxt] < npoint:
                print("inf")
                return
            q.append((nxt, npoint, nvisited))
    print(points[N])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: -float('inf'))
        self.dist[s] = 0
        self.prev = defaultdict(lambda: None)
        self.x = 0
        self.y = 0

        self.Q = []
        heappush(self.Q, (self.dist[s], s))

        c = 0
        while self.Q:
            c += 1
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, w in self.g[u]:
                alt = dist_u + w
                if self.dist[v] < alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))
            if c == 2100:
                self.x = self.dist[N]
            if c >= 5000:
                self.y = self.dist[N]
                break
    def s_d(self, goal):
        return self.dist[goal]

    def s_p(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

N, M = list(map(int, input().split()))

g_a = Graph()
for i in range(M):
    a, b, w = list(map(int, input().split()))
    g_a.add_edge(a, b, w)

s = 1
d_a = Dijkstra(g_a, s)

print("inf")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: -float('inf'))
        self.dist[s] = 0
        self.prev = defaultdict(lambda: None)
        self.x = 0
        self.y = 0

        self.Q = []
        heappush(self.Q, (self.dist[s], s))

        c = 0
        while self.Q:
            c += 1
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, w in self.g[u]:
                alt = dist_u + w
                if self.dist[v] < alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))
            if c == 2100:
                self.x = self.dist[N]
            if c >= 20000:
                self.y = self.dist[N]
                break
    def s_d(self, goal):
        return self.dist[goal]

    def s_p(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

N, M = list(map(int, input().split()))

g_a = Graph()
for i in range(M):
    a, b, w = list(map(int, input().split()))
    g_a.add_edge(a, b, w)

s = 1
d_a = Dijkstra(g_a, s)

if d_a.x == d_a.y:
    print(d_a.dist[N])
else:
    print("inf")