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 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 >= 7000:
                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")

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 >= 5001:
                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")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def bellman_ford(start):
    dist = [float("inf") for i in range(n)]
    dist[start] = 0
    for i in range(n-1):
        update = False
        for j, k, l in adj:
                if dist[k] > dist[j] + l:
                    dist[k] = dist[j] + l
                    update = True
        if not update:
            break
    negative = [False for i in range(n)]
    for j, k, l in adj:
        if dist[k] > dist[j] + l:
            negative[k] = True
    return dist,negative[n-1]
n,m = LI()
adj = []
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    adj.append([a,b,-c])
d,ne = bellman_ford(0)
if ne:
    print("inf")
else:
    print(-d[-1])
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def bellman_ford(start):
    dist = [float("inf") for i in range(n)]
    dist[start] = 0
    for i in range(2*n):
        update = False
        for j, k, l in adj:
                if dist[k] > dist[j] + l:
                    dist[k] = dist[j] + l
                    update = True
                    if i == 2*n-1:
                        return False
        if not update:
            break
    return dist
n,m = LI()
adj = []
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    adj.append([a,b,-c])
d = bellman_ford(0)
if not d:
    print("inf")
else:
    print(-d[-1])
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def bellman_ford(start):
    dist = [float("inf") for i in range(n)]
    dist[start] = 0
    for i in range(n):
        update = False
        for j, k, l in adj:
                if dist[k] > dist[j] + l:
                    dist[k] = dist[j] + l
                    update = True
                    if i == n-1:
                        return False
        if not update:
            break
    return dist
n,m = LI()
adj = []
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    adj.append([a,b,-c])
d = bellman_ford(0)
if not d:
    print("inf")
else:
    print(-d[-1])
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def bellman_ford(start):
    dist = [-float("inf") for i in range(n)]
    dist[start] = 0
    for i in range(n):
        update = False
        for j, k, l in adj:
                if dist[k] < dist[j] + l:
                    dist[k] = dist[j] + l
                    update = True
                    if i == n-1:
                        return False
        if not update:
            break
    return dist
n,m = LI()
adj = []
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    adj.append([a,b,c])
d = bellman_ford(0)
if not d:
    print("inf")
else:
    print(d[-1])
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def bellman_ford(start):
    dist = [float("inf") for i in range(n)]
    dist[start] = 0
    for i in range(n):
        update = False
        for j, k, l in adj:
                if dist[k] < dist[j] + l:
                    dist[k] = dist[j] + l
                    update = True
                    if i == n-1:
                        return False
        if not update:
            break
    return dist
n,m = LI()
adj = []
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    adj.append([a,b,c])
d = bellman_ford(0)
if not d:
    print("inf")
else:
    print(d[-1])
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def dijkstra(start):
    d = [-float("inf") for i in range(n)]
    d[start] = 0
    q = [[0,start]]
    k = 0
    while q:
        k += 1
        dx,x = q.pop(0)
        for y,dy in out[x]:
            if d[y] < dx+dy:
                d[y] = dx+dy
                q.append([d[y],y])
        if k == n*2:
            return ["inf"]*n
    return d
n,m = LI()
out = [[] for i in range(n)]
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    out[a].append([b,c])
d = dijkstra(0)
print(d[-1])
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def dijkstra(start):
    d = [-float("inf") for i in range(n)]
    d[start] = 0
    q = [[0,start]]
    k = 0
    while q:
        k += 1
        dx,x = heappop(q)
        for y,dy in out[x]:
            if d[y] < dx+dy:
                d[y] = dx+dy
                heappush(q,[d[y],y])
        if k == n*2:
            return ["inf"]*n
    return d
n,m = LI()
out = [[] for i in range(n)]
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    out[a].append([b,c])
d = dijkstra(0)
if d[-1] == -float("inf"):print(0)
else:print(d[-1])

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def dijkstra(start):
    d = [-float("inf") for i in range(n)]
    d[start] = 0
    q = [[0,start]]
    k = 0
    while q:
        k += 1
        dx,x = heappop(q)
        for y,dy in out[x]:
            if d[y] < dx+dy:
                d[y] = dx+dy
                heappush(q,[d[y],y])
        if k == n:
            return ["inf"]*n
    return d
n,m = LI()
out = [[] for i in range(n)]
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    out[a].append([b,c])
d = dijkstra(0)
if d[-1] == -float("inf"):print(ans)
else:print(d[-1])

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def dijkstra(start):
    d = [-float("inf") for i in range(n)]
    d[start] = 0
    q = [[0,start]]
    k = 0
    while q:
        k += 1
        dx,x = heappop(q)
        for y,dy in out[x]:
            if d[y] < dx+dy:
                d[y] = dx+dy
                heappush(q,[d[y],y])
        if k == n*n:
            return ["inf"]*n
    return d
n,m = LI()
out = [[] for i in range(n)]
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    out[a].append([b,c])
d = dijkstra(0)
print(d[-1])

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def dijkstra(start):
    d = [-float("inf") for i in range(n)]
    d[start] = 0
    q = [[0,start]]
    k = 0
    while q:
        k += 1
        dx,x = heappop(q)
        for y,dy in out[x]:
            if d[y] < dx+dy:
                d[y] = dx+dy
                heappush(q,[d[y],y])
        if k == n*2:
            return ["inf"]*n
    return d
n,m = LI()
out = [[] for i in range(n)]
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    out[a].append([b,c])
d = dijkstra(0)
print(d[-1])
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
e=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    e.append([a-1,b-1,-c])
M=10**18
d=[0]+[M]*~-n
k=0
while k<n*2:
    k+=1
    f=0
    for a,b,c in e:
        if d[b]>d[a]+c:
            d[b]=d[a]+c
            f=1
    if not f:
        break
else:
    print('inf')
    exit()
print(-d[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
e=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    e.append([a-1,b-1,-c])
M=10**18
d=[0]+[M]*~-n
k=0
while k<n+10:
    k+=1
    f=0
    for a,b,c in e:
        if d[b]>d[a]+c:
            d[b]=d[a]+c
            f=1
    if not f:
        break
else:
    print('inf')
    exit()
print(-d[-1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
e=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    e.append([a-1,b-1,-c])
M=10**18
d=[0]+[M]*~-n
k=0
while k<n+1:
    k+=1
    f=0
    for a,b,c in e:
        if d[b]>d[a]+c:
            d[b]=d[a]+c
            f=1
    if not f:
        break
else:
    print('inf')
    exit()
print(-d[-1])

Submission status: Wrong Answer

Solution code:
INF = 1 << 50

N, M = map(int, input().split())
E = []
d = [INF] * (N + 1)
d[1] = 0

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

ans = None

for i in range(N):
    for e in E:
        if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
            if i == N - 1:
                ans = 'inf'
                break
            d[e[1]] = d[e[0]] + e[2]
    else:
        ans = -d[N]

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
E = []
d = [1 << 50] * (N + 1)
d[1] = 0

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

ans = None

for i in range(N):
    for e in E:
        if d[e[0]] != 1 and d[e[1]] > d[e[0]] + e[2]:
            if i == N - 1:
                ans = 'inf'
                break
            d[e[1]] = d[e[0]] + e[2]
    else:
        ans = -d[N]

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
E = []
d = [float('inf')] * (N + 1)
d[1] = 0

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

ans = None

for i in range(N):
    for e in E:
        if d[e[0]] != 1 and d[e[1]] > d[e[0]] + e[2]:
            if i == N - 1:
                ans = 'inf'
                break
            d[e[1]] = d[e[0]] + e[2]
    else:
        ans = -d[N]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M = map(int, input().split())
abc = [[int(j) for j in input().split()] for _ in range(M)]

inf = float("inf")

allcost = [ -inf] * (N+1)
allcost[1] = 0

for i in range(M):
    a,b,c = abc[i]

for n in range(1, N):
    for edge in range(M):
        a,b,c = abc[edge]
        if allcost[b] < allcost[a] + c:
            allcost[b] = allcost[a] + c

for edge in range(M):
    a,b,c = abc[edge]
    if allcost[a] + c > allcost[b]:
        print("inf")
        exit(0)

print(allcost[N])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M = map(int, input().split())
abc = [[int(j) for j in input().split()] for _ in range(M)]

inf = float("inf")

allcost = [ -inf] * (N+1)
allcost[1] = 0
pred = [None] * (N+1)

for i in range(M):
    a,b,c = abc[i]

for n in range(1, N+1):
    for edge in range(M):
        a,b,c = abc[edge]
        if allcost[b] < allcost[a] + c:
            allcost[b] = allcost[a] + c
            pred[b] = a
# print(allcost)

for edge in range(M):
    a,b,c = abc[edge]
    if allcost[a] + c > allcost[b]:
        print("inf")
        exit(0)

print(allcost[N])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M = map(int, input().split())
abc = [[int(j) for j in input().split()] for _ in range(M)]

inf = float("inf")
CH = [ [] for _ in range(N+1)]
cost = [ [inf] * (N+1) for _ in range(N+1)]

allcost = [ inf] * (N+1)
allcost[1] = 0
pred = [None] * (N+1)

for i in range(M):
    a,b,c = abc[i]
    CH[a] .append(b)
    CH[b] .append(a)
    cost[a][b] = - c
    cost[b][a] = - c

for n in range(1, N+1):
    for edge in range(M):
        a,b,c = abc[edge]
        c = -c
        if allcost[b] > allcost[a] + c:
            allcost[b] = allcost[a] + c
            pred[b] = a
# print(allcost)

for edge in range(M):
    a,b,c = abc[edge]
    c = -c
    if allcost[a] + c < allcost[b]:
        print("inf")
        exit(0)

print(-allcost[N])

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
v=[]
for _ in range(M):
    v += [list(map(int,input().split()))]

for i in range(M):
    v[i][2] *= -1

dist=[10**18]*N
dist[0]=0

negative=[False]*N

t=0
for _ in range(N):
    for i in range(N):
        for j in range(N):
            for k in range(M):
                if v[k][0] == i+1:
                    if v[k][1] == j+1:
                        if dist[j] > dist[i]+v[k][2]:
                            dist[j]=dist[i]+v[k][2]
                            
                            negative[i] = True
                        if negative[j] == True:
                            negative[i] = True

if negative[N-1]==True:
    print("inf")
else:
    print(dist[N-1] *-1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
v=[]
for _ in range(M):
    v += [list(map(int,input().split()))]

for i in range(M):
    v[i][2] *= -1

dist=[10**18]*N
dist[0]=0

negative=[False]*N
negative[0]=True

for _ in range(N-1):
    for i in range(N):
        for j in range(N):
            for k in range(M):
                if v[k][0] == i+1:
                    if v[k][1] == j+1:
                        if dist[j] > dist[i]+v[k][2]:
                            dist[j]=dist[i]+v[k][2]
                            if negative[i] == True:
                                negative[j] = True

if negative[N-1]==True:
    print("inf")
else:
    print(dist[N-1] *-1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
v=[]
for _ in range(M):
    v += [list(map(int,input().split()))]

for i in range(M):
    v[i][2] *= -1

dist=[10**18]*N
dist[0]=0

negative=[False]*N
negative[0]=True

for _ in range(N-1):
    for i in range(N):
        for j in range(N):
            for k in range(M):
                if v[k][0] == i+1:
                    if v[k][1] == j+1:
                        if dist[j] > dist[i]+v[k][2]:
                            dist[j]=dist[i]+v[k][2]
                            if negative[i] == True:
                                negative[j] = True

print(negative)
if negative[N-1]==True:
    print("inf")
else:
    print(dist[N-1] *-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

#True : 負の経路が存在する
def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    d[0] = 0 
    #この始点はどこでもよい
    for i in range(n):
        for j in range(w):
            e = es[j]
            if d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                if i == n-1:
                    return True
    return False
def shortest_path(s):
    #s→iの最短距離
    # s:始点, n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    #d[i] : s→iの最短距離
    d[s] = 0
    while True:
        updata = False
        for i in range(w):
            e = es[i]
            # e: 辺iについて [from,to,cost]
            if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                updata = True
        if not updata:
            break
    return d

n,w = map(int,input().split()) #n:頂点数　w:辺の数

es = []
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())
    es.append([x-1,y-1,-z])
if find_negative_loop(n,w,es):
    print('inf')
    exit()
dj = shortest_path(0)
print(-dj[-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
edges = defaultdict(list)
for _ in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    edges[a].append((b, c))
INF = 10 ** 18

def bellman_ford():
    scores = [-INF] * N
    scores[0] = 0
    for i in range(N):
        for v in range(N):
            if scores[v] == -INF:
                continue
            for to, sc in edges[v]:
                if scores[v] + sc > scores[to]:
                    scores[to] = scores[v] + sc
                    if i == N - 1:
                        return 'inf'
    return scores[N - 1]

ans = bellman_ford()
print(ans)

Submission status: Wrong Answer

Solution code:
# D
from math import isinf
N,M = map(int, input().split())
e = []
for _ in range(M):
    a,b,c = map(int, input().split())
    e.append((a-1,b-1,-c))

dists = [float('inf')] * N # 到達不能はinf
def bellman_ford(edges:list, start:int)->bool:
    """O(|V|*|E|)
    param v:
    param edges:
    return (exist negative loop)
    """
    global dists
    dists[start] = 0
    V = len(dists)
    for i in range(V):
        for (s,t,w) in edges:
            if isinf(dists[s]): continue
            if dists[t] > dists[s]+w:
                dists[t] = dists[s]+w
                if i==V-1 and t==V-1:
                    return True
        print(dists)
    return False

negativeLoop = bellman_ford(e, 0)
if negativeLoop:
    print('inf')
else:
    print(-dists[-1])

Submission status: Wrong Answer

Solution code:
# D
from math import isinf
N,M = map(int, input().split())
e = []
for _ in range(M):
    a,b,c = map(int, input().split())
    e.append((a-1,b-1,-c))

dists = [float('inf')] * N # 到達不能はinf
def bellman_ford(edges:list, start:int)->bool:
    """O(|V|*|E|)
    param v:
    param edges:
    return (exist negative loop)
    """
    global dists
    dists[start] = 0
    V = len(dists)
    for i in range(V):
        for (s,t,w) in edges:
            if isinf(dists[s]): continue
            if dists[t] > dists[s]+w:
                dists[t] = dists[s]+w
                if i==V-1:
                    return True
        # Bprint(dists)
    return False

negativeLoop = bellman_ford(e, 0)
if negativeLoop:
    print('inf')
else:
    print(-dists[-1])

Submission status: Wrong Answer

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

rs = {}
for i in abc:
    if i[0] in rs:
        rs[i[0]][i[1]] = i[2]
    else:
        rs[i[0]] = {i[1]: i[2]}

maxn = [float('inf') * -1] * (n + 1)
maxn[1] = 0 


nr = [[1, i, {1}] for i in rs[1]]
while len(nr) != 0:
    r = nr.pop(0)
    maxn[r[1]] = max(maxn[r[1]], maxn[r[0]] + rs[r[0]][r[1]])
    if r[1] not in r[2] and r[1] in rs:
        nr += [[r[1], i, r[2].copy() | {r[1]}] for i in rs[r[1]]]
print(maxn[n])

Submission status: Wrong Answer

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

rs = {}
for i in abc:
    if i[0] in rs:
        rs[i[0]][i[1]] = i[2]
    else:
        rs[i[0]] = {i[1]: i[2]}

maxn = [float('inf') * -1] * (n + 1)
maxn[1] = 0 

inf_point = [False] * (n + 1)
nextr = [[1, i, {1}] for i in rs[1]]
count = 0
while len(nextr) != 0:
    count += 1
    r = nextr.pop(0)
    if r[1] in r[2]:
        maxn[r[1]] = float('inf')
    elif r[1] in rs:
        nextr += [[r[1], i, r[2].copy() | {r[1]}] for i in rs[r[1]]]
    if count > 4000:
        break

nextr = [[1, i, {1}] for i in rs[1]]
count = 0
while len(nextr) != 0:
    count += 1
    r = nextr.pop(0)
    maxn[r[1]] = max(maxn[r[1]], maxn[r[0]] + rs[r[0]][r[1]])
    if r[1] not in r[2] and r[1] in rs:
        nextr += [[r[1], i, r[2].copy() | {r[1]}] for i in rs[r[1]]]
    if count > 4000:
        break
print(maxn[n])