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: Runtime Error

Solution code:
#!/usr/bin/python3
# vim: set fileencoding=utf-8:
import collections

stack = collections.deque()
N, M = [int(ele) for ele in input().split()]
edges = []
adj_list = []
for _ in range(N+1):
    adj_list.append([])

d = [-1000000000000000000000000000000000000000000000000000000] * (N+1)

for _ in range(M):
    src, dst, w = [int(ele) for ele in input().split()]
    if src == 1:
        d[dst] = w
    edges.append([src, dst, w])
    adj_list[src].append(dst)

yet = [ele for ele in range(1, N+1)]
queue = collections.deque()


def main():
    global edges
    queue.append(1)
    bfs(queue)
    edges = list(filter(lambda x: x[0] not in yet or x[1] not in yet, edges))

    print(d[-1] if bellman_ford() != -1 else "inf")


def bfs(queue):
    if not queue:  # queueが空ならfalseで終了
        return

    n = queue[-1]
    yet.remove(n)

    for dst in adj_list[n]:
        if dst in yet and dst not in queue:  # 未訪問かつqueueにもない
            queue.appendleft(dst)
    else:
        queue.pop()
        bfs(queue)


def bellman_ford():
    for _ in range(N - 1):
        for src, dst, w in edges:
            if d[dst] < w + d[src]:
                d[dst] = w + d[src]

    for src, dst, w in edges:
        if d[dst] < w + d[src]:
            return -1

    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

    #edgeは1次元ですべて(始点,終点,重み)を格納
    def bellmanford(edge):
        cost = [inf] * N
        cost[0] = 0
        exist_minus_cycle = False
        for i in range(N):
            update = False
            for from_, to, cost in edge:
                cost_to = cost[from_] + cost
                if cost_to < cost[to]:
                    update = True
                    cost[to] = cost_to
                    
            if not update:
                break
            elif i==N-1:
                exist_minus_cycle = True

        #どこで無限に更新されるか判定
        minus_cycle = set()
        if exist_minus_cycle:
            for i in range(N+1):
                for from_, to, cost in edge:
                    cost_to = cost[from_] + cost
                    if from_ in minus_cycle:
                        minus_cycle.add(to)
                    if cost_to < cost[to]:
                        minus_cycle.add(from_)
                        minus_cycle.add(to)
                        cost[to] = cost_to
        return cost, minus_cycle
    
    cost,minus_cycle = bellmanford(edge)


    if N-1 in minus_cycle :
        print("inf")
    else:
        print(-cost[-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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
    
    #どこで無限に更新されるか判定
    if exist_minus_cycle:
        minus_cycle = set()
        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 or N-1 in minus_cycle:
        print("inf")
    else:
        print(-node[-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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(N):
    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: Runtime Error

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

e_list = []
for i in range(N):
    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: Runtime Error

Solution code:
# ABC 061 D
# 有向グラフ各辺のコストを集めて最大化する問題だが、全部符号を変えれば最短経路問題にできる

from typing import List
from math import isinf


class Edge(object):

    def __init__(self, src: int, dst: int, cost: int):
        self.src = src
        self.dst = dst
        self.cost = cost


class BellmanFord(object):

    def __init__(self, v_len: int, edges: List[Edge], start: int):
        """
        隣接行列を使っていないので、有向グラフにのみ適用可能。
        ベルマンフォード法によって最短経路を求める。
        ダイクストラと違って負の数も扱えるが、O(|V||E|) なのでダイクストラより遅い。

        :param v_len: グラフのノード数 通常は|V|、1-indexedなグラフなら |V| + 1
        :param edges: 辺のリスト
        :param start: 始点 単一視点最短経路問題として解くので必要
        """
        self._dist = [float('inf') for _ in range(v_len)]  # 始点から各頂点までの最短距離
        self._prev = [float('inf') for _ in range(v_len)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        self._solve(edges, start)

    def _solve(self, edges, start):
        self._dist[start] = 0

        cnt = 0
        while True:  # 更新は高々 |V| - 1 回で終わる
            cnt += 1
            updated = False
            for e in edges:
                if self._dist[e.src] + e.cost < self._dist[e.dst]:
                    self._dist[e.dst] = self._dist[e.src] + e.cost
                    self._prev[e.dst] = e.src
                    if cnt >= len(self._dist):
                        self._dist[e.dst] = float('-inf')
                    updated = True
            if not updated:
                break

    def distance(self, goal: int):
        """
        負の閉路を含む場合は -inf を返す。
        """
        return self._dist[goal]

    def path(self, goal: int):
        """
        負の閉路を含む場合は計算が終わらない。
        """
        path = list()
        path.append(goal)
        cursor = goal

        while not isinf(self._prev[cursor]):
            path.append(self._prev[cursor])
            cursor = self._prev[cursor]

        return list(reversed(path))


N, M = map(int, input().split())
edges = list()
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append(Edge(a, b, -1 * c))
bf = BellmanFord(N + 1, edges, 1)
print(-1 * bf.distance(N))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**9)

n,m = map(int, (input().split()))


checked= {}
graph = {}
for i in range(m):
    a,b,c = map(int, input().split())

    if a in graph:
        graph[a].append((b,c))
    else:
        graph[a] = []
        graph[a].append((b,c))

ans = -1*float("inf")
def solve(node, current_score):
    global ans
    if node == n:
        if n in graph:
            for tmp in graph[n]:
                if tmp[0] == 1:
                    flag = True
            if not flag:
                if ans < current_score:
                    ans = current_score 
            else:
                print("inf")
                exit()
        else:
            if ans < current_score:
                ans = current_score 

    if node in graph:
        for g in graph[node]:
            solve(g[0], current_score + g[1])


solve(1,0)
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int, (input().split()))


checked= {}
graph = {}
for i in range(m):
    a,b,c = map(int, input().split())

    if a in graph:
        graph[a].append((b,c))
    else:
        graph[a] = []
        graph[a].append((b,c))

ans = -1*float("inf")
def solve(node, current_score):
    global ans
    if node == n:
        if n in graph:
            for tmp in graph[n]:
                if tmp[0] == 1:
                    flag = True
            if not flag:
                if ans < current_score:
                    ans = current_score 
            else:
                print("inf")
                exit()
        else:
            if ans < current_score:
                ans = current_score 

    if node in graph:
        for g in graph[node]:
            solve(g[0], current_score + g[1])


solve(1,0)
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
edge=[]
for i in range(m):
    a, b, c = map(int, input().split())
    edge.append([a,b,-c])

def BellmanFord(edges,num_v,source):
  #グラフの初期化
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  #辺の緩和
  for i in range(num_v):
    for e in edges:
      if e[0] != inf and dist[e[1]-1] > dist[e[0]-1] + e[2]:
        dist[e[1]-1] = dist[e[0]-1] + e[2]
        if i == num_v-1:dist[e[1]-1] = inf

  return dist

d = BellmanFord(edge,n,1)

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

Submission status: Runtime Error

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

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

for _ in range(N-1):
	for i in range(M):
		if d[a[i]-1]==INF:
			continue
		if d[b[i]-1]>d[a[i]-1]+c[i]:
			d[b[i]-1] = d[a[i]-1] + c[i]

ans = -d[N-1]

negative = [False]*N
for _ in range(N):
	for i in range(M):
		if d[a[i]-1]==INF:
			continue
		if d[b[i]-1]>d[a[i]-1]+c[i]:
			d[b[i]-1] = d[a[i]-1] + c[i]
			negative[i] = True
		if negative[a[i]-1]==True:
			negative[b[i]-1] = True

if negative[N-1]==True:
	print('inf')
else:
	print(ans)

Submission status: Runtime Error

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

dw = [ [] for i in range(N) ]


for a,b,c in li:
  dw[a].append( (b,c) )

NOT = 1e+10 -1 
  
cost = [NOT]*N
cost[0]=0
cosli = []
for i in range(1000):
  chk = [0]*N
  now = 0
  pop=[now]
  for i in range(N):
    now = pop.pop()
    chk[now]=1
    for b,c in dw[now]:
      if ( cost[b] == NOT ):
        cost[b] = cost[now] + c
      else:
        cost[b] = max(cost[now] + c,cost[b])
      if (chk[b]==0):
        pop.append(b)
  cosli.append( cost[N-1] )  

if ( cosli[-1] != cosli[-2] ):
  print ("inf")
else:
  print (cosli[-1])

Submission status: Runtime Error

Solution code:
from collections import deque


n, m = map(int, input().split())
tree = [[] for i in range(n)]
path = {}
for i in range(m):
    tmp1, tmp2, cost = map(int, input().split())
    tree[tmp1-1].append([tmp2-1, cost])

q = deque()
q.append([-1, 0])
pos_cost = [-10**10]*n
pos_cost[0] = 0
path = {}

def judge(start):
    q2 = deque()
    q2.append(start)
    visited = [False]*n
    visited[start] = True
    while q2:
        pos = q2.popleft()
        for next_pos, cost in tree[pos]:
            if not visited[next_pos]:
                q.append(next_pos)
                visited[next_pos] = True
    if visited[n-1]:
        print("inf")
        exit()

while q:
    prev_pos, pos = q.popleft()
    if prev_pos*10000 + pos in path:
        judge(pos)
        continue
    path[prev_pos*10000 + pos] = 1
    for next_pos, cost in tree[pos]:
        if pos_cost[pos] + cost > pos_cost[next_pos]:
            pos_cost[next_pos] = pos_cost[pos] + cost
            q.append([pos, next_pos])
print(pos_cost[n-1])

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc061/tasks/abc061_d



# coding: utf-8
# Your code here!

#input_template
inpPh = 3
debug = True
debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    print(f'selected_input({inpPh}):\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), input().split() ) )
else:
    N,M = tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), input().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,-ci))

vlist =[ None for _ in range(N)]    

        
s_loc,g_loc = 0, N-1

vlist[s_loc] = 0
#print(vlist)




is_inf = False
for i in range(len(vlist)):
    for e in elist:
        a,b,c = e
        if vlist[a] == None:
            continue
        elif vlist[b] == None or vlist[b] > vlist[a] + c:
            vlist[b] = vlist[a] + c
            if i == N-1 and b == N-1:
                pass
                is_inf = True
                 
res = -vlist[g_loc]            


if is_inf:
    print('inf')
else:
    print(res)

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc061/tasks/abc061_d



# coding: utf-8
# Your code here!

#input_template
inpPh = 2
debug = True
debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    print('selected_input:\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), input().split() ) )
else:
    N,M =tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), input().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,ci))

vlist =[ [None,[]] for _ in range(N)]    

for e in elist:
    a,b,c = e
    vlist[a][1].append((a,b,-c))
        
s_loc,g_loc = 0, N-1

vlist[s_loc][0] = 0
#print(vlist)

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g0 = vlist[g_loc][0]            

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g1 = vlist[g_loc][0]  

if g0 != g1:
    print('inf',end='')
else:
    print(-g0,end='')

#print('res',g0,g1)
for v in vlist:
    #print(v)        
    pass

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc061/tasks/abc061_d



# coding: utf-8
# Your code here!

#input_template
inpPh = 2
debug = True
debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    print('selected_input:\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), input().split() ) )
else:
    N,M =tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), input().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,ci))

vlist =[ [None,[]] for _ in range(N)]    

for e in elist:
    a,b,c = e
    vlist[a][1].append((a,b,-c))
        
s_loc,g_loc = 0, N-1

vlist[s_loc][0] = 0
#print(vlist)

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g0 = vlist[g_loc][0]            

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g1 = vlist[g_loc][0]  

if g0 != g1:
    print('inf')
else:
    print(-g0)

#print('res',g0,g1)
for v in vlist:
    #print(v)        
    pass

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc061/tasks/abc061_d



# coding: utf-8
# Your code here!

#input_template
inpPh = 1
debug = True
debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    print('selected_input:\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), input().split() ) )
else:
    N,M =tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), input().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,ci))

vlist =[ [None,[]] for _ in range(N)]    

for e in elist:
    a,b,c = e
    vlist[a][1].append((a,b,-c))
        
s_loc,g_loc = 0, N-1

vlist[s_loc][0] = 0
#print(vlist)

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g0 = vlist[g_loc][0]            

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g1 = vlist[g_loc][0]  

if g0 != g1:
    print('inf')
else:
    print(-g0)

#print('res',g0,g1)
for v in vlist:
    #print(v)        
    pass

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc061/tasks/abc061_d



# coding: utf-8
# Your code here!

#input_template
inpPh = 2
debug = True
#debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    print('selected_input:\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = map(int, sys.stdin.readline().split())
else:
    N,M = map(int, sys.stdin.readline().split())

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = map(int, sys.stdin.readline().split())
    else:
        ai,bi,ci = map(int, sys.stdin.readline().split())
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,ci))

vlist =[ [None,[]] for _ in range(N)]    

for e in elist:
    a,b,c = e
    vlist[a][1].append((a,b,-c))
        
s_loc,g_loc = 0, N-1

vlist[s_loc][0] = 0
#print(vlist)

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g0 = vlist[g_loc][0]            

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v3_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g1 = vlist[g_loc][0]  

if g0 != g1:
    print('inf')
else:
    print(-g0)

#print('res',g0,g1)
for v in vlist:
    #print(v)        
    pass

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc061/tasks/abc061_d

import sys

# coding: utf-8
# Your code here!

#input_template
inpPh = 2
debug = True
debug = False
if not debug:
    inpPh = 0



    
inploc = inpPh - 1 #0,1,2



inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), sys.stdin.readline().split() ) )
else:
    N,M =tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), sys.stdin.readline().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,ci))

vlist =[ [None,[]] for _ in range(N)]    

for e in elist:
    a,b,c = e
    vlist[a][1].append((a,b,-c))
        
s_loc,g_loc = 0, N-1

vlist[s_loc][0] = 0
#print(vlist)

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g0 = vlist[g_loc][0]            

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v3_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g1 = vlist[g_loc][0]  

if g0 != g1:
    print('inf')
else:
    print(-g0)

#print('res',g0,g1)
for v in vlist:
    #print(v)        
    pass

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc061/tasks/abc061_d



# coding: utf-8
# Your code here!

#input_template
inpPh = 2
debug = True
debug = False
if not debug:
    inpPh = 0





inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    print('selected_input:\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), sys.stdin.readline().split() ) )
else:
    N,M =tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), sys.stdin.readline().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,ci))

vlist =[ [None,[]] for _ in range(N)]    

for e in elist:
    a,b,c = e
    vlist[a][1].append((a,b,-c))
        
s_loc,g_loc = 0, N-1

vlist[s_loc][0] = 0
#print(vlist)

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g0 = vlist[g_loc][0]            

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v3_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g1 = vlist[g_loc][0]  

if g0 != g1:
    print('inf')
else:
    print(-g0)

#print('res',g0,g1)
for v in vlist:
    #print(v)        
    pass

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc061/tasks/abc061_d



# coding: utf-8
# Your code here!

#input_template
inpPh = 2
debug = True
debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    print('selected_input:\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), sys.stdin.readline().split() ) )
else:
    N,M =tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), sys.stdin.readline().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,ci))

vlist =[ [None,[]] for _ in range(N)]    

for e in elist:
    a,b,c = e
    vlist[a][1].append((a,b,-c))
        
s_loc,g_loc = 0, N-1

vlist[s_loc][0] = 0
#print(vlist)

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g0 = vlist[g_loc][0]            

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v3_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g1 = vlist[g_loc][0]  

if g0 != g1:
    print('inf')
else:
    print(-g0)

#print('res',g0,g1)
for v in vlist:
    #print(v)        
    pass