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 math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                if i == N - 1:
                    exist_minus_cycle = True
                    break
        if not update:
            break
    
    #どこで無限に更新されるか判定
    minus_cycle = set()
    if exist_minus_cycle:
        for i in range(N):
            for from_, to, cost in edge:
                node_to = node[from_] + cost
                if from_ in minus_cycle:
                    minus_cycle.add(to)
                if node_to < node[to]:
                    minus_cycle.add(to)
                    node[to] = node_to
        
    if 0 in minus_cycle :
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                if i == N - 1:
                    exist_minus_cycle = True
                    break
        if not update:
            break
    
    #どこで無限に更新されるか判定
    minus_cycle = set()
    if exist_minus_cycle:
        for i in range(N):
            for from_, to, cost in edge:
                node_to = node[from_] + cost
                if from_ in minus_cycle:
                    minus_cycle.add(to)
                elif node_to < node[to]:
                    minus_cycle.add(to)
                    node[to] = node_to
        
    if 0 in minus_cycle :
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                if i == N - 1:
                    exist_minus_cycle = True
                    break
        if not update:
            break
    
    #どこで無限に更新されるか判定
    minus_cycle = set()
    for i in range(N):
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                minus_cycle.add(to)
                node[to] = node_to
        
    if 0 in minus_cycle:
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                if i == N - 1:
                    exist_minus_cycle = True
                    break
        if not update:
            break
    
    #どこで無限に更新されるか判定
    minus_cycle = set()
    for i in range(N):
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                minus_cycle.add(to)
                node[to] = node_to
        
    print(minus_cycle)
    if 0 in minus_cycle:
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    exist_minus_cycle = False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                if i == N - 1:
                    exist_minus_cycle = True
                    break
        if not update:
            break
    
    #どこで無限に更新されるか判定
    minus_cycle = set()
    for i in range(N):
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                minus_cycle.add(to)
                node[to] = node_to
        if not minus_cycle:
            break

    if 0 in minus_cycle:
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def BELLMANFORD(point,d,n):
    cost       = {node:-float("inf")for node in range(1,n+1)}
    preference = {node:None         for node in range(1,n+1)}      #最適路のこと 
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
 
    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定
        for now,lis in d.copy().items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
                    negative[now-1]=1
 
    return cost,negative


def main():
    n,m=map(int,input().split())
    d=defaultdict(list)
    for i in range(m):
        a,b,c=map(int,input().split())
        d[a].append([b,c])
    x,y=(BELLMANFORD(1,d,n))
    if sum(y)>0:
        print("inf")
    else:
        print(x[n])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    minus_cycle = False
    contin = set([0]) 
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            if from_ not in contin:
                continue
            contin.add(to)
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                if i == N - 1:
                    minus_cycle = True
                    break
        if not update:
            break

    if minus_cycle:
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    minus_cycle=False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node[from_]!=inf and node_to < node[to]:
                update = True
                node[to] = node_to
                if i == N - 1:
                    minus_cycle = True
                    break
        if not update:
            break

    if minus_cycle:
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = []
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge.append((a, b, -c))
    node = [inf] * N
    node[0] = 0
    minus_cycle=False
    for i in range(N):
        update = False
        for from_, to, cost in edge:
            node_to = node[from_] + cost
            if node_to < node[to]:
                update = True
                node[to] = node_to
                if i == N - 1:
                    minus_cycle = True
                    break
        if not update:
            break

    
    if minus_cycle:
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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+1):
    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: return -1

  return dist


#%%
N,M = [int(x) for x in input().split()]
edges = []
for _ in range(M):
    l = [int(x) for x in input().split()]
    l[2]*=-1
    edges.append(l)
#%%
route = BellmanFord(edges,N,1)
if(route == -1):
    print('inf')
else:
    print(-int(route[N-1]))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

def BellmanFord(edges,num_v,source):
  #グラフの初期化
  inf=10**20
  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

#%%
N,M = [int(x) for x in input().split()]
edges = []
for _ in range(M):
    l = [int(x) for x in input().split()]
    l[2]*=-1
    edges.append(l)
edges.sort(key=itemgetter(0))
#%%
route = BellmanFord(edges,N,1)
if(route == -1):
    print('inf')
else:
    print(-int(route[-1]))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

#%%
N,M = [int(x) for x in input().split()]
edges = []
for _ in range(M):
    l = [int(x) for x in input().split()]
    l[2]*=-1
    edges.append(l)
edges.sort(key=itemgetter(0))
#%%
route = BellmanFord(edges,N,1)
if(route == -1):
    print('inf')
else:
    print(-int(route[-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 -1
  
  return dist


#%%
N,M = [int(x) for x in input().split()]
edges = []
for _ in range(M):
    l = [int(x) for x in input().split()]
    l[2]*=-1
    edges.append(l)
    
#%%
route = BellmanFord(edges,N,1)
if(route == -1):
    print('inf')
else:
    print(-route[-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 -1

  return dist

N,M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()]for _ in range(M)]

route = BellmanFord(edges,N,1)
if(route == -1):
    print('inf')
else:
    print(route[-1])

Submission status: Wrong Answer

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


def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [int(10**20)] * (n+1)
    d[1] = 0 
    #この始点はどこでもよい
    for i in range(n*2+1):
        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*2:
                    return "inf"
                    
    return -d[n]
print(find_negative_loop(N,M,es))

Submission status: Wrong Answer

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


def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [int(10**20)] * (n+1)
    d[1] = 0 
    #この始点はどこでもよい
    for i in range(n+1):
        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:
                    return "inf"
                    
    return -d[n]
print(find_negative_loop(N,M,es))

Submission status: Wrong Answer

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


def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [int(10**20)] * (n+1)
    d[1] = 0 
    #この始点はどこでもよい
    for i in range(n+1):
        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 "inf"
                    
    return -d[n]
print(find_negative_loop(N,M,es))

Submission status: Wrong Answer

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

#ベルマンフォードO(V*E)
def bellman_ford(V,G,start=0):
    dist = [inf]*V
    dist[start]=0
    negative_cycle = False
    for _ in range(1,V):
        for u in G:
            for v,d in G[u]:
                if dist[v]>dist[u]+d:
                    dist[v] = dist[u]+d
    for u in G:
        for v,d in G[u]:
            if dist[v] > dist[u]+d:
                negative_cycle=True
    if negative_cycle:
        return -1
    else:
        return dist

V,E = map(int,input().split())
G = defaultdict(list)
for i in range(E):
    u,v,d = map(int,input().split())
    G[u-1].append((v-1,-d))
d = bellman_ford(V,G,0)
if d==-1:
    print("inf")
else:
    print(-1*d[V-1])

Submission status: Wrong Answer

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

#ベルマンフォードO(V*E)
def bellman_ford(V,G,start=0):
    dist = [inf]*V
    dist[start]=0
    negative_cycle = False
    for _ in range(V):
        for u in G:
            for v,d in G[u]:
                if dist[v]>dist[u]+d:
                    dist[v] = dist[u]+d
    for u in G:
        for v,d in G[u]:
            if dist[v] > dist[u]+d:
                negative_cycle=True
    if negative_cycle:
        return -1
    else:
        return dist

V,E = map(int,input().split())
G = defaultdict(list)
for i in range(E):
    u,v,d = map(int,input().split())
    G[u-1].append((v-1,-d))
d = bellman_ford(V,G,0)
if d==-1:
    print("inf")
else:
    print(-1*d[V-1])

Submission status: Wrong Answer

Solution code:
def bellman_ford(x, V, E):
    V[x][0] = 0
    for i in range(len(V) - 2):
        for a, b, c in E:
            if V[b][0] > V[a][0] + c:
                V[b][0] = V[a][0] + c
                V[b][1] = a
    for a, b, c in E:
        if V[b][0] > V[a][0] + c:
            return None
    return V

INF = 10 ** 15
n, m = map(int, input().split())
V = [[INF, 0] for _ in range(n + 1)]
E = []
for i in range(m):
    ai, bi, ci = map(int, input().split())
    E.append([ai, bi, -ci])
V = bellman_ford(1, V, E)
if V is None:
    print('inf')
else:
    i = n
    ans = 0
    while(i != 1):
        d, i = V[i]
        ans += d
    print(-V[n][0])

Submission status: Wrong Answer

Solution code:
def dfs(i, V, E):
    S = [i, i]
    while(len(S) > 1):
        vi = S.pop()
        d = V[vi]
        for j, value in E[vi].items():
            if j in S:
                V[-1] = None
                return V

            if V[j] < value + d:
                V[j] = value + d
                S.append(j)
    return V

INF = 10 ** 15
n, m = map(int, input().split())
V = [-INF for _ in range(n + 1)]
E = [{} for _ in range(n + 1)]
for i in range(m):
    ai, bi, ci = map(int, input().split())
    E[ai][bi] = ci
V[1] = 0
V = dfs(1, V, E)
if V[-1] is None:
    print('inf')
else:
    print(V[-1])

Submission status: Wrong Answer

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

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

vi=0
min_dis_list = [10**27 for i in range(N)]
min_dis_list[vi] = 0
prev_list = [-1 for i in range(N)]

for i in range(N-1):
    for e in e_list:
        u,v,d = e
        if min_dis_list[v]>min_dis_list[u]+d:
            min_dis_list[v]=min_dis_list[u]+d
            prev_list[v]=u

neg_loop_flag=False
for e in e_list:
    u,v,d = e
    if min_dis_list[u] + d < min_dis_list[v]:
        neg_loop_flag=True
        break
if neg_loop_flag:
    print("inf")
else:
    print(-min_dis_list[N-1])

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
edge=[list(map(int,input().split())) for i in range(M)]
inf=10**12
f=lambda i,j,w: [i-1,j-1,-w]
edge=[f(i,j,w) for i,j,w in edge]
def bf(N,start):
    d=[inf]*N
    d[start]=0
    prev=[-1]*N
    for i in range(N-1):
        f=0
        for i,j,w in edge:
            if d[j]>d[i]+w:
                d[j]=d[i]+w
                prev[j]=i
                f=1
        if f==0:
            break
    while True:
        f=0
        for i,j,w in edge:
            if d[j]>d[i]+w and (d[j]!=-inf or d[i]!=-inf):
                d[i]=d[j]=-inf
                f=1
        if f==0:
            break
    return d
d=bf(N,0)

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

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
edge=[list(map(int,input().split())) for i in range(M)]
inf=10**12
c=[[] for i in range(N)]
for i,j,w in edge:
    c[i-1].append((j-1,w))
d=[-inf]*N
v=[0]*N
import sys
sys.setrecursionlimit(10**6)
def dfs(p,v,d):
    for n,w in c[p]:
        if v[n]==0:
            d[n]=max(d[n],d[p]+w)
            v[n]=1
            loop=dfs(n,v,d)
            if loop:
                return 1
            v[n]=0
        else:
            if d[p]+w>d[n]:
                return 1
    return 0
d[0]=0
v[0]=1
loop=dfs(0,v,d)
if loop:
    print('inf')
else:
    print(d[N-1])

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
edge=[list(map(int,input().split())) for i in range(M)]
inf=10**12
c=[[] for i in range(N)]
for i,j,w in edge:
    c[i-1].append((j-1,w))
start=0
d=[-inf]*N
d[start]=0
v=[0]*N
import sys
sys.setrecursionlimit(10**6)
loop=0
def dfs(p,v,d):
    for n,w in c[p]:
        if v[n]==0:
            d[n]=max(d[n],d[p]+w)
            v[n]=1
            loop=dfs(n,v,d)
            if loop:
                return 1
            v[n]=0
        else:
            return 1
v[0]=1
loop=dfs(start,v,d)
if loop:
    print('inf')
else:
    print(d[N-1])

Submission status: Wrong Answer

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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

ABC = [[int(x) for x in input().split()] for _ in range(M)]
row,col,val = zip(*ABC)

# -1倍しておいて最短路問題にする
val = [-x for x in val]

# 求めたい経路の外の閉路にはまるとまずい
#graph = csr_matrix((val,(row,col)),(N+1,N+1))
#try:
#  dist = bellman_ford(graph,indices = [1])[0].astype(int)
#  answer = -dist[N]
#except:
#  answer = 'inf'
import numpy as np
from scipy.sparse.csgraph import connected_components

graph = csr_matrix((val,(row,col)),(N+1,N+1))

find_component_graph = csr_matrix(([1]*M,(row,col)),(N+1,N+1))
_,labels = connected_components(find_component_graph,connection = 'strong')
idx = (labels == labels[1])

graph = graph[idx,:][:,idx]

try:
  dist = bellman_ford(graph,indices = [0])[0].astype(int)
  answer = -dist[-1]
except:
  answer = 'inf'

print(answer)

Submission status: Wrong Answer

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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

ABC = [[int(x) for x in input().split()] for _ in range(M)]
row,col,val = zip(*ABC)

# -1倍しておいて最短路問題にする
val = [-x for x in val]

# 求めたい経路の外の閉路にはまるとまずい
#graph = csr_matrix((val,(row,col)),(N+1,N+1))
#try:
#  dist = bellman_ford(graph,indices = [1])[0].astype(int)
#  answer = -dist[N]
#except:
#  answer = 'inf'
import numpy as np
from scipy.sparse.csgraph import connected_components
row += (N,)
col += (1,)
val += (np.inf,)

graph = csr_matrix((val,(row,col)),(N+1,N+1))
_,labels = connected_components(graph,connection = 'strong')
idx = (labels == labels[1])

graph2 = graph[idx,:][:,idx]
graph2 = graph[idx,:][:,idx]

try:
  dist = bellman_ford(graph2,indices = [0])[0].astype(int)
  answer = -dist[-1]
except:
  answer = 'inf'

print(answer)