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:
n, m = map(int, input().split())
d = []
for i in range(m):#h:高さ
    d.append([int(m) for m in input().split()])
e = []
for i in range(m):
    e.append([])
for i in range(m):
    e[i].append(d[i][0] - 1)
    e[i].append(d[i][1] - 1)
    e[i].append(-d[i][2])
#edges = d
#num_v = n
#source = m


#ベルマンフォード
#高々|V|-1回で最安定経路にたどり着くっていうのがなかなか理解できなくて、紙に書きながら理解した。

"""edge = [[0,1,2],[0,2,5],[1,2,4],[1,3,6],[1,4,10],[2,3,2],[3,5,1],[4,5,3],[4,6,5],[5,6,9],
       [1,0,2],[2,0,5],[2,1,4],[3,1,6],[4,1,10],[3,2,2],[5,3,1],[5,4,3],[6,4,5],[6,5,9]]"""
edge = e

def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    for i in range(num_v):
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
        if i == num_v - 1:
            d[n - 1] = -inf
            break
    return d

print(-shortest_path(edge,n,0)[n - 1])

#print(BellmanFord(e, n, m))

Submission status: Wrong Answer

Solution code:
def BF(p,n,s):
    inf=float("inf")
    d=[inf for i in range(n)]
    d[s-1]=0
    for i in range(n+1):
        for e in p:
            if e[0]!=inf and d[e[1]-1]>d[e[0]-1]+e[2]:
                d[e[1]-1] = d[e[0]-1] + e[2]
                if i==n: return [0,'inf']
    return list(map(lambda x:-x, d))
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(m)]
a=[[x,y,-z] for x,y,z in a]
print(BF(a, n, 1)[-1])

Submission status: Wrong Answer

Solution code:
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 [0,'inf']
    return list(map(lambda x:-x, dist))
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(m)]
a=[[x,y,-z] for x,y,z in a]
print(BellmanFord(a, n, 1)[-1])

Submission status: Wrong Answer

Solution code:
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 [0,'inf']
    return dist
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(m)]
a=[[x,y,-z] for x,y,z in a]
print(BellmanFord(a, n, 1)[-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
inf = 10**9+1
n,m = map(int, input().split())
edge = []
for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a,b,c))

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[b]<inf:
                d[b] = max(d[b], d[a]+c)
            else:
                d[b] = d[a] + c

ans = d[n-1]
updated = [False for _ in range(n)]
for _ in range(n):
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[a]+c>d[b]:
                d[b] = d[a] + c
                updated[b] = True
        if updated[a]:
            updated[b] = True

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
inf = 10**9+1
n,m = map(int, input().split())
edge = []
for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a,b,c))

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[b]<inf:
                d[b] = max(d[b], d[a]+c)
            else:
                d[b] = d[a] + c

ans = d[n-1]
updated = [False for _ in range(n)]
for _ in range(n):
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[a]+c>d[b]:
                d[b] = d[a] + c
                updated[a] = True
        if updated[a]:
            updated[b] = True

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
inf = 10**9+1
n,m = map(int, input().split())
edge = []
for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a,b,c))

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[b]<inf:
                d[b] = max(d[b], d[a]+c)
            else:
                d[b] = d[a] + c

ans = d[n-1]

for _ in range(n):
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf and d[b]<inf:
            if d[b]<inf:
                d[b] = max(d[b], d[a]+c)
            else:
                d[b] = d[a] + c

if d[n-1]>ans:
    print("inf")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def BF(N, edges, start):
    D = {}
    P = {}
    for i in range(N):
        P[i] = None
        if i == start:
            D[i] = 0
        else:
            D[i] = float("inf")
    
    for i in range(N):
        for edge in edges:
            a, b, c = edge
            if D[b] > D[a] + c:
                D[b] = D[a] + c
                P[b] = a
                if i == N-1:
                    return False
    
    D = {}
    P = {}
    for i in range(N):
        P[i] = None
        if i == start:
            D[i] = 0
        else:
            D[i] = float("inf")

    for i in range(N-1):
        for edge in edges:
            a, b, c = edge
            if D[b] > D[a] + c:
                D[b] = D[a] + c
                P[b] = a
    return (D, P)

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

if BF(N, edges, 0) :
    (D, P) = BF(N, edges, 0) 
    print(-D[N - 1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = {}
    for i in range(N):
        graph[i] = {}
        for j in range(N):
            graph[i][j] = 0
    for edge in edges:
        a, b, c = edge
        graph[a][b] = c
    return graph

def BF(N, edges, start):
    D = {}
    P = {}
    for i in range(N):
        P[i] = None
        if i == start:
            D[i] = 0
        else:
            D[i] = float("inf")
    for i in range(N):
        for edge in edges:
            a, b, c = edge
            if D[b] > D[a] + c:
                D[b] = D[a] + c
                P[b] = a

    for edge in edges:
        a, b, c = edge
        if D[a] + c < D[b]:
            return False

    return (D, P)

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

if BF(N, edges, 0) :
    (D, P) = BF(N, edges, 0) 
    print(-D[N - 1])
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
edges=[]
for m in range(M):
  a,b,c=map(int,input().split())
  edges.append([a-1,b-1,-c])
inf=float("inf")
dist=[inf for i in range(N)]
dist[0]=0
for i in range(N):
  for e in edges:
    if dist[e[1]]>dist[e[0]]+e[2]:
      dist[e[1]]=dist[e[0]]+e[2]
      if i==N-1:
        print(inf)
        exit()
print(-dist[N-1])

Submission status: Wrong Answer

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

edge=[[] for _ in range(N)]
dist=[-float('inf') for _ in range(N)]
dist[0]=0

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

tmp=-float('inf')
for n in range(N):
    flag=0
    for i in range(N):
        for b,p in edge[i]:
            if dist[b]<dist[i]+p:
                dist[b]=dist[i]+p
                flag=1
    tmp=dist[-1]
    if flag==0:
        break
if tmp!=dist[-1]:
    print('inf')
else:
    print(int(dist[-1]))

Submission status: Wrong Answer

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

edge=[[] for _ in range(N)]
dist=[-float('inf') for _ in range(N)]
dist[0]=0

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

for n in range(N):
    flag=0
    for i in range(N):
        for b,p in edge[i]:
            if dist[b]<dist[i]+p:
                dist[b]=dist[i]+p
                flag=1
    if flag==0:
        break
if flag==1:
    print('inf')
else:
    print(dist[-1])

Submission status: Wrong Answer

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

edge=[[] for _ in range(N)]
dist=[-float('inf') for _ in range(N)]
dist[0]=0

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

for n in range(N-1):
    flag=0
    for i in range(N):
        for b,p in edge[i]:
            if dist[b]<dist[i]+p:
                dist[b]=dist[i]+p
                flag=1
    if flag==0:
        break
if flag==1:
    print('inf')
else:
    print(dist[-1])

Submission status: Wrong Answer

Solution code:
V, E=map(int,input().strip().split(' '))
edge=[]
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    edge.append([at,bt,ct])

#edge=[[0,1,2],[0,2,5],[1,2,4],[1,3,6],[2,3,2],[1,4,10],[3,5,1],[4,5,3],[4,6,5],[5,6,9],[1,0,2],[2,0,5],[2,1,4],[3,1,6],[3,2,2],[4,1,10],[5,3,1],[5,4,3],[6,4,5],[6,5,9]]
#V=7
#E=10*2
inf=-3*10**15

def shortest_path(s):
    d=[inf]*V
    d[s]=0
    for _ in range(V+1):
        update=False
        for i in range(E):
            if d[edge[i][0]-1]!=inf and d[edge[i][1]-1]<d[edge[i][0]-1]+edge[i][2]:
                d[edge[i][1]-1]=d[edge[i][0]-1]+edge[i][2]
                update=True
        if update==False:
            break
        if _ == V:
            return False
    return d

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

Submission status: Wrong Answer

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


def initialize_int(adj, s):
    """
    assume that all vertex in {0, 1, 2, ..., N - 1}
    """
    N = len(adj)
    MAX_NUM = float('inf')
    d = [MAX_NUM] * N
    d[s] = 0
    parent = [None] * N
    return d, parent


def relax(d, w, source_v, target_v, parent):
    new_cost = d[source_v] + w[source_v][target_v]
    if new_cost < d[target_v]:
        d[target_v] = new_cost
        parent[target_v] = source_v


# Even if a negative weight exists, bellman-ford can find shortest paths.
# it also detects negative cycles,
# but not every edges that consist the negative cycles is stored.
# time complexity: O(VE + (V^2))
def bellman_ford(adj, w, s):
    d, parent = initialize_int(adj, s)
    # calculate shortest paths
    for _ in range(len(adj)):
        for vertex in range(len(adj)):
            for neighbor in adj[vertex]:
                relax(d, w, vertex, neighbor, parent)

    # detects negative cycles if exist
    negative_cycle_edges = set()
    for vertex in range(len(adj)):
        for neighbor in adj[vertex]:
            if d[neighbor] > d[vertex] + w[vertex][neighbor]:
                negative_cycle_edges.add((vertex, neighbor))
    return d, parent, negative_cycle_edges


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]

for _ in range(M):
    a, b, c = [int(elem) for elem in fin().split()]
    a -= 1
    b -= 1
    c *= -1
    adj[a].append(b)
    w[a][b] = c

d, parent, negative_cycle_edges = bellman_ford(adj, w, 0)
if len(negative_cycle_edges) > 0:
    negative_cycle_edges = {(source, target) for source, target in negative_cycle_edges}
    # see if there's a path from 0 to this edge via DFS
    stack = [0]
    visited = set()
    visited.add(0)
    while stack:
        source = stack.pop()
        for neighbor in adj[source]:
            if (source, neighbor) in negative_cycle_edges:
                print("inf")
                exit(0)
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    print(-d[N - 1])
else:
    print(-d[N - 1])

Submission status: Wrong Answer

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


def initialize_int(adj, s):
    """
    assume that all vertex in {0, 1, 2, ..., N - 1}
    """
    N = len(adj)
    MAX_NUM = float('inf')
    d = [MAX_NUM] * N
    d[s] = 0
    parent = [None] * N
    return d, parent


def relax(d, w, source_v, target_v, parent):
    new_cost = d[source_v] + w[source_v][target_v]
    if new_cost < d[target_v]:
        d[target_v] = new_cost
        parent[target_v] = source_v


# Even if a negative weight exists, bellman-ford can find shortest paths.
# it also detects negative cycles,
# but not every edges that consist the negative cycles is stored.
# time complexity: O(VE + (V^2))
def bellman_ford(adj, w, s):
    d, parent = initialize_int(adj, s)
    # calculate shortest paths
    for _ in range(len(adj)):
        for vertex in range(len(adj)):
            for neighbor in adj[vertex]:
                relax(d, w, vertex, neighbor, parent)

    # detects negative cycles if exist
    negative_cycle_edges = set()
    for vertex in range(len(adj)):
        for neighbor in adj[vertex]:
            if d[neighbor] > d[vertex] + w[vertex][neighbor]:
                negative_cycle_edges.add((vertex, neighbor))
    return d, parent, negative_cycle_edges


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]

for _ in range(M):
    a, b, c = [int(elem) for elem in fin().split()]
    a -= 1
    b -= 1
    c *= -1
    adj[a].append(b)
    w[a][b] = c

d, parent, negative_cycle_edges = bellman_ford(adj, w, 0)
if negative_cycle_edges:
    print("inf")
else:
    print(-d[N - 1])

Submission status: Wrong Answer

Solution code:

import queue

class Graph:

    INF = 10**27+1
    
    def __init__(self,v_num,is_directed = False):
        self.is_directed = is_directed
        self.v_num = v_num
        self.E = []
        self.v_s_list = [[] for i in range(self.v_num)]
        
    def appendEdge(self,v1,v2,weight=1):
        if max(v1,v2,self.v_num-1)>=self.v_num or min(v1,v2)<0:
            print("ERROR: The vertex ID is wrong.")
            return False

        self.E.append([v1,v2,weight])
        
        if self.is_directed:
            self.v_s_list[v1].append([v2,weight])
        else:
            self.v_s_list[v1].append([v2,weight])
            self.v_s_list[v2].append([v1,weight])
        
        
    def BFS(self,v,usage="SSSP"):
        is_processed = [False for i in range(self.v_num)]
        distance_list = [Graph.INF for i in range(self.v_num)]
        Q = queue.Queue()
        Q.put(v)
        is_processed[v]=True
        distance_list[v] = 0
        while not Q.empty():
            v1 = Q.get()
            for v2 in self.v_s_list[v1]:
                if not is_processed[v2[0]]:
                    is_processed[v2[0]] = True
                    distance_list[v2[0]] = min(distance_list[v1]+1,distance_list[v2[0]])
                    Q.put(v2[0])
        if usage=="SSSP":
            return distance_list
        elif usage=="ConnectedComponent":
            cc_list = []
            for i in range(self.v_num):
                if is_processed[i]:
                    cc_list.append(i)
            return cc_list

    def getSSSPwithBFS(self,v):
        return self.BFS(v,"SSSP")
        
    def getConnectedComponent(self,v):
        return self.BFS(v,"ConnectedComponent")
        
    def getSSSPwithBellmanFord(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]

        for i in range(self.v_num):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if distance_list[v2] > distance_list[v1] + d:
                    distance_list[v2] = distance_list[v1] + d
                    pre_list[v2] = v1
        
        for e in self.E:
            v1 = e[0]
            v2 = e[1]
            d = e[2]
            if d + distance_list[v1] < distance_list[v2]:
                return None
        
        return distance_list, pre_list


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

G = Graph(N,True)

for i in range(M):
    a,b,c = list(map(int,input().split()))
    G.appendEdge(a-1,b-1,-c)
    
res=G.getSSSPwithBellmanFord(0)

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

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
import copy

N, M = inpl()
inf = float('inf')
path = dict([])
score = [-inf]*N
score[0] = 0
goalscore =[inf]*N
for _ in range(M):
    a, b, c = inpl()
    path[(a-1, b-1)] = c

now = [False for _ in range(N+1)]
now[0] = True 
for i in range(N):
    now1 = copy.deepcopy(now)
    now = [False for _ in range(N)]
    score1 = copy.deepcopy(score)
    for (na, nb), nc in path.items():
        if not now1[na]:
            continue
        score[nb] = max(score1[nb], score[na]+nc)
        now[nb] = True
    if i == N-2:
        goalscore = copy.deepcopy(score)
    if goalscore == score and i != N-2:
        break
print(score[N-1] if goalscore == score else 'inf')

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
import copy

N, M = inpl()
inf = float('inf')
path = dict([])
score = [-inf]*N
score[0] = 0
goalscore =[inf]*N
for _ in range(M):
    a, b, c = inpl()
    path[(a-1, b-1)] = c

now = [False for _ in range(2*N)]
now[0] = True 
for i in range(N+1):
    now1 = copy.deepcopy(now)
    now = [False for _ in range(N)]
    score1 = copy.deepcopy(score)
    for (na, nb), nc in path.items():
        if not now1[na]:
            continue
        score[nb] = max(score1[nb], score[na]+nc)
        now[nb] = True
    if i == N-1:
        goalscore = copy.deepcopy(score)
    if goalscore == score and i != N-1:
        break
print(score[N-1] if goalscore == score else 'inf')

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
import copy

N, M = inpl()
inf = float('inf')
path = dict([])
score = [-inf]*N
score[0] = 0
for _ in range(M):
    a, b, c = inpl()
    path[(a-1, b-1)] = c

now = [False for _ in range(N)]
now[0] = True 
for i in range(N+1):
    now1 = copy.deepcopy(now)
    now = [False for _ in range(N)]
    score1 = copy.deepcopy(score)
    for (na, nb), nc in path.items():
        if not now1[na]:
            continue
        score[nb] = max(score1[nb], score[na]+nc)
        now[nb] = True
    if i == N-1:
        goalscore = copy.deepcopy(score)

print(score[N-1] if goalscore == score else 'inf')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
loop = False
for j in range(E):
    From,To,cost = edge[j]
    if d[From] != inf and d[To]>d[From]+cost:
        loop = True
        break

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
def shortest_path(s,d):
    for i in range(V):
        for j in range(E):
            From,To,cost = edge[j]
            if d[From] != inf and d[To]>d[From]+cost:
                d[To]=d[From]+cost                
    return d
d = [inf]*V
d[0] = 0
d = shortest_path(0,d)
d_ = shortest_path(0,d)
if d[N-1]!=d_[N-1]:
    print('inf')
else:
    print(-d[N-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
def shortest_path(s):
    d = [inf]*V
    d[s]=0
    for i in range(V):
        for j in range(E):
            From,To,cost = edge[j]
            if d[From] != inf and d[To]>d[From]+cost:
                d[To]=d[From]+cost
                if i == V-1:
                    return d, True                
    return d,False
d,loop = shortest_path(0)
if loop:
    print('inf')
else:
    print(-d[N-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
def shortest_path(s):
    d = [inf]*V
    d[s]=0
    for i in range(V):
        update = False
        for j in range(E):
            From,To,cost = edge[j]
            if d[From] != inf and d[To]>d[From]+cost:
                d[To]=d[From]+cost
                update = True
        if not update:
            break
    loop = i == V-1
    return d,loop
d,loop = shortest_path(0)
if loop:
    print('inf')
else:
    print(-d[N-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
def shortest_path(s):
    d = [inf]*V
    d[s]=0
    for i in range(V+2):
        update = False
        for j in range(E):
            From,To,cost = edge[j]
            if d[From] != inf and d[To]>d[From]+cost:
                d[To]=d[From]+cost
                update = True
        if not update:
            break
    loop = i == V+1
    return d,loop
d,loop = shortest_path(0)
if loop:
    print('inf')
else:
    print(-d[N-1])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
edge = [0]*M
for i in range(M):
    a,b,c=map(int,input().split())
    a -= 1
    b -= 1
    c *= -1
    edge[i] = (a,b,c)

inf = float('inf')
V = N
E = M
def shortest_path(s):
    d = [inf]*V
    d[s]=0
    for i in range(V+1):
        update = False
        for j in range(E):
            From,To,cost = edge[j]
            if d[From] != inf and d[To]>d[From]+cost:
                d[To]=d[From]+cost
                update = True
        if not update:
            break
    loop = i == V
    return d,loop
d,loop = shortest_path(0)
if loop:
    print('inf')
else:
    print(-d[N-1])

Submission status: Wrong Answer

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

INF = float("inf")
d = [INF] * N
d[0] = 0
for i in range(N):
    for a in range(N):
        for b, c in G[a]:
            if d[b] > d[a] + c:
                d[b] = d[a] + c

ne = [False] * N
ans = -d[N - 1]
for i in range(N):
    for a in range(N):
        for b, c in G[a]:
            if d[b] > d[a] + c:
                ne[b] = True
                d[b] = d[a] + c

            if ne[i]:
                ne[b] = True

if ne[N - 1]:
    print("inf")
else:
    print(ans)

Submission status: Wrong Answer

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

INF = float("inf")
d = [INF] * N
d[0] = 0
for i in range(N):
    for b, c in G[i]:
        if d[b] > d[i] + c:
            d[b] = d[i] + c

mi = [False] * N
ans = -d[N - 1]
for i in range(N):
    for b, c in G[i]:
        if d[b] > d[i] + c:
            d[b] = d[i] + c
            mi[b] = True

        if mi[i]:
            mi[b] = True

if mi[N - 1]:
    print("inf")
else:
    print(ans)

Submission status: Wrong Answer

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

INF = float("inf")
d = [INF] * N
d[0] = 0
for i in range(N):
    for b, c in G[i]:
        if d[b] > d[i] + c:
            d[b] = d[i] + c

mi = [False] * N
for i in range(N):
    for b, c in G[i]:
        if d[b] > d[i] + c:
            mi[b] = True

        if mi[i]:
            mi[b] = True

if mi[N - 1]:
    print("inf")
else:
    print(-d[N - 1])

Submission status: Wrong Answer

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

INF = float("inf")
d = [INF] * N
d[0] = 0
for i in range(N):
    for b, c in G[i]:
        if d[b] > d[i] + c:
            d[b] = d[i] + c

mi = [False] * N
for i in range(N):
    for b, c in G[i]:
        if d[b] > d[i] + c:
            mi[b] = True

if mi[N - 1]:
    print("inf")
else:
    print(-d[N - 1])

Submission status: Wrong Answer

Solution code:
# ABC 061 D
# Bellman-Ford
N, M = map(int, input().split())
INF = float("inf")

G = []
# from a to b cost c
for k in range(M):
    a, b, c = map(int, input().split())
    G.append([a-1,b-1,-c])

dist = [INF for k in range(N)]
dist[0] = 0

for k in range(N-1):
    for l in range(M):
        a, b, c = G[l][0], G[l][1], G[l][2]
        if dist[a] != INF and dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
ans = -dist[N-1]

# find a negative loop
dist = [0 for k in range(N)]
flag = 0
for k in range(N):
    for l in range(M):
        a, b, c = G[l][0], G[l][1], G[l][2]
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            if k == N-1:
                flag = 1

print("inf" if flag else ans)

Submission status: Wrong Answer

Solution code:
# ABC 061 D
# Bellman-Ford

N, M = map(int, input().split())
INF = float("inf")

G = []
# from a to b cost c
for k in range(M):
    a, b, c = map(int, input().split())
    G.append([a-1,b-1,-c])

dist = [INF for k in range(N)]
dist[0] = 0

for k in range(N-1):
    for l in range(M):
        a, b, c = G[l][0], G[l][1], G[l][2]
        if dist[a] != INF and dist[b] > dist[a] + c:
            dist[b] = dist[a] + c

# find a negative loop
negative = [0 for k in range(N)]
for k in range(N):
    for l in range(M):
        a, b, c = G[l][0], G[l][1], G[l][2]
        if dist[a] != INF and dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            negative[b] = 1
        if negative[a] == 1:
            negative[b] = 0

print("inf" if negative[N-1] else -dist[N-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n, m = ai()

from collections import defaultdict as dd

edge = dd(list)
for _ in range(m):
    a, b, c = ai()
    edge[a - 1].append([b - 1, -c])


dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v, c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
            if i >= n-1 and v == n-1:
                print('inf')
                exit()
    i += 1
    if i > n + 2:
        break
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n, m = ai()

from collections import defaultdict as dd

edge = dd(list)
for _ in range(m):
    a, b, c = ai()
    edge[a - 1].append([b - 1, -c])


dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v, c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
            if i >= n-1 and v == n-1:
                print('inf')
                exit()
    i += 1
    if i > n+1:
        break
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n, m = ai()

from collections import defaultdict as dd

edge = dd(list)
for _ in range(m):
    a, b, c = ai()
    edge[a - 1].append([b - 1, -c])


dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v, c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
            if i > n and v == n-1:
                print('inf')
                exit()
    i += 1
    if i > n+1:
        break
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n, m = ai()

from collections import defaultdict as dd

edge = dd(list)
for _ in range(m):
    a, b, c = ai()
    edge[a - 1].append([b - 1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v, c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
            if i == n and v == n-1:
                print('inf')
                exit()
    i += 1
    if i > n:
        break
print(-dist[-1])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

n, m = ai()

from collections import defaultdict as dd

edge = dd(list)
for _ in range(m):
    a, b, c = ai()
    edge[a - 1].append([b - 1, -c])

dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
    cur_v = vs.pop()
    for v, c in edge[cur_v]:
        if dist[v] > dist[cur_v] + c:
            dist[v] = dist[cur_v] + c
            vs.add(v)
            if i == n-1 and v == n-1:
                print('inf')
                exit()
    i += 1
    if i > n:
        break
print(-dist[-1])