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:
import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]*N# iに到達するときの最大得点
moji=[1]+[0]*(N-1)#infなら0をかえす
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji[b[m]-1]=1
 
moji2=[0]*N
for n in range(N):
  for m in moji:
    u=a[m]
    v=b[m]
    if V[a[m]-1]+c[m]>V[b[m]-1]:
      V[b[m]-1]=V[a[m]-1]+c[m]
      moji2[b[m]-1]=1
    if moji2[a[m]-1]:
      moji2[b[m]-1]=1
if moji2[N-1]:
  print("inf")
else:
  print(V[N-1])

Submission status: Runtime Error

Solution code:
import collections
import heapq
import math


class GraphLoopException(Exception):
    pass


class WeightedDigraph:
    def __init__(self):
        self.__vertices = set()
        self.__edges = collections.defaultdict(list)
        self.__weights = {}

    @property
    def vertices(self):
        return self.__vertices

    @property
    def edges(self):
        return self.__edges

    def neighbors(self, v):
        return self.__edges[v]

    def weight(self, u, v):
        return self.__weights[(u, v)]

    def add_vertex(self, label):
        self.__vertices.add(label)

    def add_edge(self, begin, end, weight):
        self.__edges[begin].append(end)
        self.__weights[(begin, end)] = weight


def dijkstra(graph, start):
    queue = []
    closed = set()
    dist = dict.fromkeys(graph.vertices, math.inf)
    prev = dict.fromkeys(graph.vertices, None)

    heapq.heappush(queue, (0, start))
    dist[start] = 0

    while len(queue) != 0:
        _, v = heapq.heappop(queue)
        closed.add(v)

        for u in graph.neighbors(v):
            cost = dist[v] + graph.weight(v, u)
            if u not in closed and u not in [_[1] for _ in queue]:
                prev[u] = v
                dist[u] = cost
                heapq.heappush(queue, (cost, u))
            elif u in [_[1] for _ in queue]:
                if cost < dist[u]:
                    prev[u] = v
                    dist[u] = cost

    return dist, prev


def bellman_ford(graph, start):
    dist = dict.fromkeys(graph.vertices, math.inf)
    prev = dict.fromkeys(graph.vertices, None)
    dist[start] = 0
    for i in range(len(graph.vertices)):
        for v in graph.vertices:
            for u in graph.neighbors(v):
                cost = dist[v] + graph.weight(v, u)
                if dist[v] != math.inf and dist[u] > cost:
                    prev[u] = v
                    dist[u] = cost
                    if i == len(graph.vertices) - 1:
                        raise GraphLoopException

    return dist, prev

def cyclic(graph):
    """Return True if the directed graph has a cycle.
    The graph must be represented as a dictionary mapping vertices to
    iterables of neighbouring vertices. For example:

    >>> cyclic({1: (2,), 2: (3,), 3: (1,)})
    True
    >>> cyclic({1: (2,), 2: (3,), 3: (4,)})
    False

    """
    visited = set()
    path = [object()]
    path_set = set(path)
    stack = [iter(graph.edges)]
    while stack:
        for v in stack[-1]:
            if v in path_set:
                return True
            elif v not in visited:
                visited.add(v)
                path.append(v)
                path_set.add(v)
                stack.append(iter(graph.edges.get(v, ())))
                break
        else:
            path_set.remove(path.pop())
            stack.pop()
    return False


def main():
    g = WeightedDigraph()

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

    for i in range(m):
        a, b, c = map(int, input().split())
        g.add_vertex(a)
        g.add_vertex(b)
        g.add_edge(a, b, -c)

    if cyclic(g):
        print('inf')
    else:
        print(-bellman_ford(g, 1)[0][n])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

from collections import defaultdict
E = []

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

def reachable_vertices(neighbor, s):
  V = set()
  V.add(s)
  stack=[s]
  while stack:
    v = stack.pop()
    for u in neighbor[v]:
      if u not in V:
        V.add(u)
        stack.append(u)
  return V

def neighbor_dict(E):
  neighbor = defaultdict(list)
  for a,b,c in E:
    neighbor[a].append(b)
  return neighbor

def rev_neighbor_dict(E):
  neighbor = defaultdict(list)
  for a,b,c in E:
    neighbor[b].append(a)
  return neighbor

def degenerate_graph(V, E):
  d = {v:i for i,v in enumerate(sorted(V))}
  return len(V), [(d[a],d[b],c) for a,b,c in E]

# only vertices that are reachable from 1 or N
N,E = degenerate_graph(reachable_vertices(neighbor_dict(E), 0), E)
N,E = degenerate_graph(reachable_vertices(rev_neighbor_dict(E), N-1), E)
score = [float('-inf')]*N
score[0] = 0


i = 0
updated=True
while updated:
  if i == N:
    print('inf')
    break

  updated = False
  for a,b,w in E:
    if score[b] < score[a] + w:
      score[b] = score[a] + w
      updated = True
  i += 1
else:
  print(score[N-1])

Submission status: Runtime Error

Solution code:
import math

INF = float("inf")

V, E = map(int, input().split())
es = []

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

d = [INF] * V
d[1] = 0

for _ in range(V - 1):
    updated = False
    for e in es:
        if math.isinf(d[e[0]]):
            continue
        if d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            updated = True
    if not updated:
        break

negative = [False] * V

for _ in range(V):
    for e in es:
        if math.isinf(d[e[0]]):
            continue
        if d[e[1]] > d[e[0]] + e[2]:
            negative[e[1]] = True
            d[e[1]] = d[e[0]] + e[2]
        elif negative[e[1]]:
            d[e[1]] = True
print(-d[V] if not negative[V] else "inf")

Submission status: Runtime Error

Solution code:
import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]*N# iに到達するときの最大得点
moji=[1]+[0]*(N-1)#infなら0をかえす
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji[b[m]-1]=1
 
moji2=[0]*N
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=W[a[m]-1]+c[m]
        moji2[b[m]-1]=1
    if moji2[a[m-]1]:
      moji2[b[m]-1]
if moji2[N-1]:
  print("inf")
else:
  print(V[N-1])

Submission status: Runtime Error

Solution code:
import math

INF = float("inf")

V, E = map(int, input().split())
es = []

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

d = [INF] * V
d[1] = 0

updated = False
for _ in range(V - 1):
    for e in es:
        if math.isinf(d[e[0]]):
            continue
        if d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
    if not updated:
        break

negative = [False] * V

for _ in range(V):
    for e in es:
        if math.isinf(d[e[0]]):
            continue
        if d[e[1]] > d[e[0]] + e[2]:
            negative[e[1]] = True
            d[e[1]] = d[e[0]] + e[2]
        elif negative[e[1]]:
            d[e[1]] = True
print(-d[V] if not negative[V] else "inf")

Submission status: Runtime Error

Solution code:
def trans(cur, prev_paths, score, goal_score, paths, N):
    # inf check
    if cur in prev_paths:
        return 'inf'
    if cur == N:
        goal_score = score
    if not cur in paths:
        return goal_score

    nodes = paths[cur]
    score_updated = False
    for n, s in nodes:
        new_score = score + s
        new_prev_paths = dict(prev_paths)
        new_prev_paths[cur] = 1
        tmp_goal_score = trans(n, new_prev_paths, new_score, goal_score, paths, N)
        if tmp_goal_score == 'inf':
            return 'inf'
        elif not score_updated or tmp_goal_score > goal_score:
            goal_score = tmp_goal_score
            score_updated = True

    return goal_score


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

paths = {}
prev_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in paths:
        paths[a].append((b, c))
    else:
        paths[a] = [(b, c)] 

cur_node = 1
prev_node = -1
score = trans(cur_node, prev_paths, 0, 0, paths, N)
print(score)

Submission status: Runtime Error

Solution code:
# coding: utf-8
n,m=map(int,input().split())
score={}
muki={}
kita={}

for i in range(1,n+1):
    score[i]=0
    muki[i]=[(-1,0)]
    kita[i]=0

for i in range(m):
    a,b,c=map(int,input().split())
    if muki[a][0][0]==-1:
        muki[a]=[(b,c)]
    else:
        muki[a].append((b,c))
 
def heiro(g,moto):
    for n in muki[g]:
        if n[0]==moto:
            print('inf')
            exit()
        elif n[0]!=-1:
            heiro(n[0],moto)

for i in range(1,n+1):
    heiro(i,i)

def check(moto):
    for p in muki[moto]:
        if kita[p[0]]==0 or score[p[0]]<score[moto]+p[1]:
            score[p[0]]=score[moto]+p[1]
            kita[p[0]]+=1
        if muki[p[0]][0][0]!=-1:
            check(p[0])
            
check(1)
print(score[n])

Submission status: Runtime Error

Solution code:
import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]*N# iに到達するときの最大得点
moji=[1]+[0]*(N-1)#infなら0をかえす
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji[b[m]-1]=1

W=V[]
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        W[b[m]-1]=max(W[b[m]-1],W[a[m]-1]+c[m])
      else:
        W[b[m]-1]=W[a[m]-1]+c[m]
        moji[b[m]-1]=1
if V[N-1]==W[N-1]:
  print(V[N-1])
else:
  print("inf")

Submission status: Runtime Error

Solution code:
def trans(cur, prev_paths, score, goal_score, paths, N):
    # inf check
    if cur in prev_paths:
        return 'inf'
    if cur == N:
        goal_score = score
    if not cur in paths:
        return goal_score

    nodes = paths[cur]
    for n, s in nodes:
        new_score = score + s
        new_prev_paths = dict(prev_paths)
        new_prev_paths[cur] = 1
        tmp_goal_score = trans(n, new_prev_paths, new_score, goal_score, paths, N)
        if tmp_goal_score == 'inf':
            return 'inf'
        elif tmp_goal_score > goal_score:
            goal_score = tmp_goal_score

    return goal_score


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

paths = {}
prev_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in paths:
        paths[a].append((b, c))
    else:
        paths[a] = [(b, c)] 

cur_node = 1
prev_node = -1
score = trans(cur_node, prev_paths, 0, 0, paths, N)
print(score)

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())
a = []
b = []
c = []
for i in range(M):
    temp0, temp1, temp2= map(int, raw_input().split())
    a.append(temp0)
    b.append(temp1)
    c.append(temp2)


def search(path, target, score):
    result = []
    result_score = []
    for p in range(len(path)):
        for i in range(M):
            if b[i] == target:
                path_next = path[p][:]
                path_next.extend([a[i]])
                score_next = score[p] + c[i]
                if a[i] == 1:
                    result.append(path_next)
                    result_score.append(score_next)
                else:
                    # print("score_next", score_next)
                    pa, sc = search([path_next], a[i], [score_next])
                    result.append(pa)
                    result_score.extend(sc)
    # print(result, result_score)
    return result, result_score
    

path, score = search([[N]], N, [0])
# print(path)
# print(score)

print(max(score))

Submission status: Runtime Error

Solution code:
#coding=UTF-8


mozir=input()
hyo=mozir.split(' ')

N=int(hyo[0])
M=int(hyo[1])

A=[]
B=[]
Cost=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    A.append(int(hyo[0])-1)
    B.append(int(hyo[1])-1)
    Cost.append(int(hyo[2]))
    
#先ず得点が正になるループを探す
eipap=False
for idx in range(0,N,1):
    tansaku=[(idx,0)]
    while len(tansaku) > 0:
        next_tansaku=[]
        for mono in tansaku:
            for idy in range(0,M,1):
                if A[idy]==mono[0]:
                    #add only if better
                    appendp=True
                    for butu in next_tansaku:
                        if B[idy] == butu[0]:
                            #already exsists
                            appendp=False
                            if butu[1] > mono[1]+Cost[idy]:
                                butu[1]=mono[1]+Cost[idy]
                    if appendp:
                        next_tansaku.append((B[idy],mono[1]+Cost[idy]))
        #print(next_tansaku)
        
        for tenn in next_tansaku:
            if tenn[0]==idx and tenn[1]>0:
                eipap=True
                break

        if eipap:
            break
        else:
            tansaku=next_tansaku

if eipap:
    print('inf')
else:
    #無ければ、普通の経路探索のようなことをする
    tmp_score=[None]*N #マイナス点のときもある
    tmp_score[0]=0
    tansaku=[0]
    while len(tansaku) > 0:
        next_tansaku=[]
        for mono in tansaku:
            for idy in range(0,M,1):
                if A[idy]==mono:
                    kouho_ten=tmp_score[mono]+Cost[idy]
                    if tmp_score[B[idy]] == None or kouho_ten > tmp_score[B[idy]]:
                        tmp_score[B[idy]]=kouho_ten
                        next_tansaku.append(B[idy])

        tansaku=next_tansaku

    print(tmp_score[N-1])

Submission status: Runtime Error

Solution code:
# coding: utf-8
n,m=map(int,input().split())
score={}
muki={}
kita={}

for i in range(1,n+1):
    score[i]=0
    muki[i]=[(-1,0)]
    kita[i]=0

for i in range(m):
    a,b,c=map(int,input().split())
    if muki[a][0][0]==-1:
        muki[a]=[(b,c)]
    else:
        muki[a].append((b,c))
        
def heiro(g,moto):
    for n in muki[g]:
        if n[0]==moto:
            print('inf')
            exit()
        elif n[0]!=-1:
            heiro(n[0],moto)

for i in range(1,n+1):
    heiro(i,i)

Submission status: Runtime Error

Solution code:
def update_score_dfs(target):
    global graph, visited, scores
    visited[target] = 1
    for node, score in graph[target].items():
        if scores[target] + score > scores[node]:
            scores[node] = scores[target] + score
    for nextnode in graph[target].keys():
        if visited[nextnode] == 1:
            break
        update_score_dfs(nextnode)

n, m = map(int, raw_input().split())
graph = {}
visited = {}
# 0: not visited, 1: visited
scores = {}
for i in range(n):
    visited[i + 1] = 0
    scores[i + 1] = -float('inf')

for i in range(n):
    graph[i+1] = {}

for i in range(m):
    a, b, c = map(int, raw_input().split())
    graph[a][b] = c
    # {1: {2: 4, 3: 5}, 2: {3: 4}}

visited[n] = 1
target = 1
for node, score in graph[target].items():
    scores[node] = score
     
update_score_dfs(target)
print scores[n]

Submission status: Runtime Error

Solution code:
# coding: utf-8
n,m=map(int,input().split())
data=[]
dic={}
muki={}
kita={}
for i in range(1,n+1):
    dic[i]=0
    muki[i]=[(-1,0)]
    kita[i]=0

def heiroCheck(moto,m):
    for i in muki[moto]:
        if i[0]!=m:
            if i[0]!=-1:
                heiroCheck(i[0],m)
        else:
            print('inf')
            exit()

for i in range(m):
    a,b,c=map(int,input().split())
    if muki[a][0]!=(-1,0):
        muki[a].append((b,c))
    else:
        muki[a]=[(b,c)]

for i in range(1,n+1):
    heiroCheck(i,i)

def check(moto):
    for p in muki[moto]:
        if kita[p[0]]==0 or dic[p[0]]<dic[moto]+p[1]:
            dic[p[0]]=dic[moto]+p[1]
            kita[p[0]]+=1
        if muki[p[0]][0][0]!=-1:
            check(p[0])
            
check(1)
print(dic[n])

Submission status: Runtime Error

Solution code:
from math import inf
N, M = map(int, input().split())

l = [[] for _ in range(N)]

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

def a_max(a, b):
    if a is None:
        return b
    elif b is None:
        return a
    else:
        return max(a, b)

def contains(q, t):
    for p in q:
        if p[0] == t:
            return True
    return False

def r(p, score, q, has_loop=False):
    for i in range(len(q)):
        if q[i][0] == p:
            if q[i][1] < score:
                score = inf
                has_loop=True
                if contains(q, 0):
                    print('inf')
                    import sys
                    sys.exit(0)
                break
            else:
                return None
    #
    if p == 0:
        if has_loop:
            return score
        else:
            max_score = score
            q.append((p, score))
            for np, w in l[p]:
                if (not has_loop) or p != np:
                    max_score = a_max(max_score, r(np, score + w, q, True))
            q.pop()
            return max_score
            
    elif score is None:
        return None
    elif len(l[p]) == 0:
        return None
    #
    max_score = None
    q.append((p, score))
    for np, w in l[p]:
        contain = contains(q, np)
        if not has_loop or not contain:
            max_score = a_max(max_score, r(np, score + w, q, has_loop or contain))
    q.pop()
    return max_score

print(r(N-1, 0, []))

Submission status: Runtime Error

Solution code:
import sys

def solve(node, sc, ps, inf_check, goal_cnt):
    global inf
    if goal_cnt == 0 and sc > max_score[node]:
        max_score[node] = sc
    if node == N:
        goal_cnt += 1
        if inf_check:
            inf = True
        if goal_cnt >= 2:
            return
    for n in path[node]:
        if n in ps:
            if max_score[n] < sc + score["{} {}".format(node, n)]:
                inf_check = True
                if node == N:
                    inf = True
        else:
            ps.add(n)
            solve(n, sc + score["{} {}".format(node, n)], ps, inf_check, goal_cnt)
            ps.remove(n)
            
    return
            

N, M = map(int, input().split())
a, b, c = [0], [0], [0]
max_score = [0, 0]
path = {}
score = {}
inf = False

for num in range(1, N+1):
    path[num] = []
    max_score.append(-10000000000000)

for num in range(M):
    t1, t2, t3 = map(int, input().split())
    a.append(t1)
    b.append(t2)
    c.append(t3)
    path[t1].append(t2)
    score["{} {}".format(t1, t2)] = t3

solve(1, 0, set([1]), False, 0)

if inf:
    print('inf')
else:
    print(max_score[N])

Submission status: Runtime Error

Solution code:
def trans(cur, prev, score, paths, N):
    # inf check
    if cur in prev_paths:
        return 'inf'
    if cur == N and not cur in paths:
        return score

    nodes = paths[cur]
    for n, s in nodes:
        score += s
        prev_paths[cur] = 1
        return trans(n, prev_paths, score, paths, N)


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

paths = {}
prev_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in paths:
        paths[a].append((b, c))
    else:
        paths[a] = [(b, c)] 

cur_node = 1
prev_node = -1
score = trans(cur_node, prev_paths, 0, paths, N)
print(score)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
def main():
    N, M = map(int, input().split())

    MAP = [[0]*N for x in range(N)]
    E = []
    for m in range(M):
        a,b,c = map(int, input().split())
        MAP[a-1][b-1] = c
        E.append((a-1,b-1,c))

    dp = [-float('inf')]*N
    dp[0] = 0
    updated = set([0])
    for count in range(1, 2*N+1):  # N
        preupdated = list(updated)
        updated = set([])
        for e in preupdated:
            a,b,c = E[e]
            if max(dp[b], dp[b]) < dp[a] + c:
                updated.add(b)
                dp[b] = dp[a] + c
        if count == N-1:
            tmp = dp[N-1]

    # print(tmp, dp[N-1])
    if dp[N-1] == tmp:
        print(tmp)
    else:
        print('inf')


if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

def has_loop_f(now, path_dic, weight_dic, visited_path):
    next_cand = path_dic[now]

    if len(next_cand) == 0:
        return (False, ([], 0))

    # sys.stderr.write(str(next_cand))
    # sys.stderr.write("\n")
    for next_v in next_cand:
        if next_v in visited_path:
            weight = 0
            start_v = next_v
            now_v = next_v
            loop_path = [now_v]
            for v in visited_path[::-1]:
                weight += weight_dic[(now_v, v)]
                loop_path.append(v)
                if v == start_v:
                    break
                else:
                    now_v = v
            return (True, (loop_path[::-1], weight))
        else:
            next_visited_path = visited_path + [next_v]
            # sys.stderr.write(str((next_v, next_visited_path)))
            # sys.stderr.write("\n")
            b, tpl = has_loop_f(next_v, path_dic, weight_dic, next_visited_path)
            if b == True and tpl[1] > 0:
                return (b, tpl)
            else:
                continue

    return (False, ([], 0))

def calc_max_weight(end, rev_path_dic, weight_dic):
    if end == 1:
        return 0
    else:
        return max([calc_max_weight(prev, rev_path_dic, weight_dic) + weight_dic[(prev, end)] for prev in rev_path_dic[end]])

def main():
    line = sys.stdin.readline()
    lst = line.split()
    n = int(lst[0])
    m = int(lst[1])

    weight_dic = {}
    path_dic = defaultdict(list)
    rev_path_dic = defaultdict(list)
    for line in sys.stdin:
        lst = line.split()
        a = int(lst[0])
        b = int(lst[1])
        c = int(lst[2])
        path_dic[a].append(b)
        rev_path_dic[b].append(a)
        weight_dic[(a,b)] = c

    #まずは回路を検出
    # sys.stderr.write(str((1, [1])))
    # sys.stderr.write("\n")
    b, (loop_path, loop_weight) = has_loop_f(1, path_dic, weight_dic, [1])
    if b == True and loop_weight > 0:
        print("inf")
        return 0
    elif b == True and loop_weight <= 0:
        e = loop_path[-2]
        b = loop_path[-1]
        weight_dic[(e, b)] = 0
        rev_path_dic[b] = [i for i in rev_path_dic[b] if i != e]
        path_dic[e] = [i for i in path_dic[e] if i != b]

    ans = calc_max_weight(n, rev_path_dic, weight_dic)
    print("%d" % ans)
    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Runtime Error

Solution code:
from math import inf
N, M = map(int, input().split())

l = [[] for _ in range(N)]

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

def a_max(a, b):
    if a is None:
        return b
    elif b is None:
        return a
    else:
        return max(a, b)

def contains(q, t):
    for p in q:
        if p[0] == t:
            return True
    return False

def r(p, score, q, has_loop=False):
    for i in range(len(q)):
        if q[i][0] == p:
            if q[i][1] < score:
                score = inf
                has_loop=True
            else:
                return None
    #
    if p == 0:
        if has_loop:
            return score
        else:
            max_score = score
            q.append((p, score))
            for np, w in l[p]:
                if (not has_loop) or p != np:
                    max_score = a_max(max_score, r(np, score + w, q, True))
            q.pop()
            return max_score
            
    elif score is None:
        return None
    elif len(l[p]) == 0:
        return None
    #
    max_score = None
    q.append((p, score))
    for np, w in l[p]:
        contain = contains(q, np)
        if not has_loop or not contain:
            max_score = a_max(max_score, r(np, score + w, q, has_loop or contain))
    q.pop()
    return max_score

print(r(N-1, 0, []))

Submission status: Runtime Error

Solution code:
import math

def int_input():
    line = input()
    return [int(x) for x in line.split()]

n, m = int_input()
graph = {}

for i in range(n):
    graph[i+1] = {}

for i in range(m):
    a, b, c = int_input()
    graph[a][b] = c

def walk(graph, current, stack, acc_score, has_loop):
    if graph[current]:
        for dest, _ in graph[current].items():
            if dest in stack:
                has_loop = True

    if current == n:
        if has_loop:
            return math.inf
        return acc_score

    if not graph[current]:
        return 0

    stack_next = stack.copy()
    stack_next[current] = True

    graph_next = graph.copy()
    del graph_next[current]

    scores = [0]
    for dest, score in graph[current].items():
        if dest not in stack:
            scores.append(walk(graph_next, dest, stack_next, acc_score+score, has_loop))

    return max(scores)

print(walk(graph, 1, {}, 0, False))

Submission status: Runtime Error

Solution code:
def dstar(use, i):
    connect = ver[i]
    use.append(i)
    for k in range(n):
        if connect[k] != 0.5:
            if k in use:
                if weigth[i] + connect[k] <= weigth[k]:
                    if k == n-1:
                        print('inf')
                        exit()
                    else:
                        weigth[k] = 10**17
                        return
                else:
                    return
            if weigth[k] < weigth[i] + connect[k]:
                weigth[k] = weigth[i] + connect[k]
            dstar(use[:], k)


n, m = [int(x) for x in input().split(' ')]
ver = [[0.5 for x in range(n)] for y in range(n)]
for i in range(m):
    a, b, c = [int(x) for x in input().split(' ')]
    ver[a-1][b-1] = c
weigth = [0] + [-10**12 for x in range(n-1)]
dstar([], 0)
if weigth[n-1] > 10**13:
    print('inf')
else:
    print(weigth[n-1])

Submission status: Runtime Error

Solution code:
import math

def int_input():
    line = input()
    return [int(x) for x in line.split()]

n, m = int_input()
graph = {}

for i in range(n):
    graph[i+1] = {}

for i in range(m):
    a, b, c = int_input()
    graph[a][b] = c

def walk(graph, current, stack, acc_score, has_loop):
    if graph[current]:
        for dest, _ in graph[current].items():
            if dest in stack:
                has_loop = True

    if current == n:
        if has_loop:
            return math.inf
        return acc_score

    if not graph[current]:
        return 0

    stack_next = stack.copy()
    stack_next[current] = True

    graph_next = graph.copy()
    del graph_next[current]

    scores = []
    for dest, score in graph[current].items():
        if dest not in stack:
            scores.append(walk(graph_next, dest, stack_next, acc_score+score, has_loop))

    return max(scores)

print(walk(graph, 1, {}, 0, False))

Submission status: Runtime Error

Solution code:
# coding: utf-8
n,m=map(int,input().split())
data=[]
dic={}
muki={}
kita={}
for i in range(1,n+1):
    dic[i]=0
    muki[i]=[(-1,0)]
    kita[i]=0

for i in range(m):
    a,b,c=map(int,input().split())
    if muki[a][0]!=(-1,0):
        muki[a].append((b,c))
    else:
        muki[a]=[(b,c)]
def check(moto):
    for p in muki[moto]:
        if kita[p[0]]==0 or dic[p[0]]<dic[moto]+p[1]:
            dic[p[0]]=dic[moto]+p[1]
            kita[p[0]]+=1
    tmp=muki[moto]
    muki[moto]=[(-2,0)]
    for p in tmp:
        if muki[p[0]][0][0]==-2:
            print('inf')
            exit()
        elif muki[p[0]][0][0]!=-1:
            check(p[0])
check(1)
print(dic[n])

Submission status: Runtime Error

Solution code:
def trans(cur, prev, score, paths, N):
    # inf check
    if cur in paths:
        nodes = paths[cur]
        for n, s in nodes:
            if prev == n:
                return 'inf'
    if cur == N:
        return score

    nodes = paths[cur]
    for n, s in nodes:
        score += s
        return trans(n, cur, score, paths, N)


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

paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in paths:
        paths[a].append((b, c))
    else:
        paths[a] = [(b, c)] 

cur_node = 1
prev_node = -1
score = trans(cur_node, prev_node, 0, paths, N)
print(score)