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: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,m = LI()
    e = collections.defaultdict(list)
    for _ in range(m):
        a,b,c = LI_()
        e[a].append((b,c+1))

    t = [0] * n

    def search(s):
        d = collections.defaultdict(lambda: -inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s, -1))
        v = [{} for _ in range(n)]
        while len(q):
            k, u, mu = heapq.heappop(q)
            if mu in v[u] and v[u][mu] >= -k:
                continue
            if mu in v[u]:
                v[u][mu] = inf
            else:
                v[u][mu] = -k

            for uv, ud in e[u]:
                vd = -k + ud
                if u in v[uv] and v[uv][u] >= vd:
                    continue
                heapq.heappush(q, (-vd, uv, u))

        return v

    d = search(0)
    if max(d[n-1].values()) == inf:
        return 'inf'
    return max(d[n-1].values())


print(main())

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
D = [map(int, raw_input().split()) for _ in range(M)]

score = [None for _ in range(N+1)]
score[1] = 0

for _ in range(N):
    for a, b, c in D:
        if score[a] != None:
            score[b] = max(score[b], score[a] + c)
v1 = score[-1]
for _ in range(N):
    for a, b, c in D:
        if score[a] != None:
            score[b] = max(score[b], score[a] + c)
v2 = score[-1]

if v1 != v2:
    print "inf"
else:
    print v2

Submission status: Accepted

Solution code:
# D
from collections import deque

# create graph
G = dict()
G_inv = dict()
N, M = map(int, input().split())
for n in range(1, N+1):
    G[n] = dict()
    G_inv[n] = dict()

for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c
    G_inv[b][a] = c

# value
values = [-1000000000*2000]*(N+1)
values[1] = 0

reachable = [0]*(N+1)
reachable[N] = 1
# find reachble points
dr = deque([N])
while len(dr) > 0:
    b = dr.popleft()
    for a in G_inv[b].keys():
        if reachable[a] == 0:
            reachable[a] = 1
            dr.append(a)

# BFS
inc_cnt = 0
d = deque([1])
while len(d) > 0:
    a = d.popleft()
    for b in G[a].keys():
        if values[b] < values[a] + G[a][b] and reachable[b] == 1:
            values[b] = values[a] + G[a][b]
            inc_cnt += 1
            d.append(b)
    if inc_cnt > 2000:
        break
if inc_cnt > 1000:
    print('inf')
else:
    print(values[N])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
gr = {}
edge = []
wt = {}
for v in range(1, n + 1):
    gr[v] = []
for _ in range(m):
    a, b, c = map(int, input().split())
    gr[a].append(b)
    edge.append((a, b))
    wt[(a, b)] = c
costs = [-1e15 for _ in range(n + 1)]
costs[1] = 0

for i in range(m):
    for u, v in edge:
        if costs[v] < costs[u] + wt[(u, v)]:
            costs[v] = costs[u] + wt[(u, v)]
tmp = costs[n]
for i in range(m):
    for u, v in edge:
        if costs[v] < costs[u] + wt[(u, v)]:
            costs[v] = costs[u] + wt[(u, v)]
if tmp < costs[n]:
    print('inf')
else:
    print(costs[n])

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
g = [[] for i in xrange(n)]
for i in xrange(m):
    a, b, c = map(int, raw_input().split())
    g[a-1].append((b-1, c))
dist = [-10**18]*n


import sys
sys.setrecursionlimit(10**6)
used = [0]*n
valid = [0]*n
memo = [None]*n
def dfs(v):
    res = 0
    if memo[v] is not None:
        return memo[v]
    for t, c in g[v]:
        if not used[t]:
            if t == n-1:
                res = 1
            used[t] = 1
            res |= dfs(t)
            used[t] = 0
    valid[v] |= res
    memo[v] = valid[v]
    return res
valid[0] = valid[n-1] = 1
used[0] = 1
dfs(0)

dist[0] = 0
for t in xrange(2*n):
    update = 0
    for v in xrange(n):
        for t, c in g[v]:
            if valid[t] and dist[v] + c > dist[t]:
                dist[t] = dist[v] + c
                update = 1
if update == 1:
    print "inf"
else:
    print dist[n-1]

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, -c))
        
dist = [float('inf') for i in range(n)]
dist[0] = 0
prev = [-1 for i in range(n)]
negative_cycle = False
for k in range(n):
    for i in range(n):
        for dst, cst in g[i]:
            src = i
            if dist[dst] > dist[src] + cst:
                dist[dst] = dist[src] + cst
                prev[dst] = src
                if k == n-1 and dst == n-1:
                    dist[dst] = -float('inf')
                    negative_cycle = True

if negative_cycle:
    print('inf')
else:
    print(-dist[n-1])

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin


def na(): return map(int, stdin.readline().split())


def ns(): return stdin.readline().strip()

def bf(es, n, start, ved):
    I = 999999999999999999
    d = [I] * n
    d[start] = 0

    for i in range(n-1):
        updated = False
        for e in es:
            if not ved[e[0]]: continue
            if not ved[e[1]]: continue
            if d[e[0]] + e[2] < d[e[1]]:
                d[e[1]] = d[e[0]] + e[2]
                updated = True
        if not updated: break
    for e in es:
        if not ved[e[0]]: continue
        if not ved[e[1]]: continue
        if d[e[0]] + e[2] < d[e[1]]:
            return None
    return d


n,m = na()
es = []

for i in range(m):
    a,b,c = na()
    es.append([a-1,b-1,-c])

ig = [[] for _ in range(n)]
for e in es:
    ig[e[1]].append(e)

ved = [False] * n
q = [n-1]
j = 0
ved[n-1] = True
while(j < len(q)):
    cur = q[j]
    for e in ig[cur]:
        if not ved[e[0]]:
            ved[e[0]] = True
            q.append(e[0])
    j += 1

res = bf(es, n, 0, ved)
if res:
    print(-res[n-1])
else:
    print("inf")

Submission status: Runtime Error

Solution code:

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

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def bellman_ford(n, es, s):
    dist = [INF] * n
    dist[s] = 0
    # 更新が止まるまで繰り返す O(V*E)
    # i度目の更新までにsを始点として0~i個の辺からなる経路が探索され、その時点の最短経路が計算される
    # 最短経路は最大でもV-1個の頂点しか通らないため、最悪でもv-1回で収束する
    while True:
        update = False
        # 辺をすべて見る
        for e in es:
            # aに到達可能かつa経由の方が近ければ更新する
            if dist[e.start] != INF and dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                update = True
        # 一度も更新されなければ終了
        if not update:
            break
    return dist

def find_negative_loop(n, es):
    dist = [0] * n
    for i in range(n):
        for e in es:
            if dist[e.end] > dist[e.start] + e.cost:
                dist[e.end] = dist[e.start] + e.cost
                if i == n - 1:
                    return True
    return False

es = []

for i in range(M):
  a, b, cost = map(int, input().split())
  es.append(Edge(a-1, b-1, -cost))
  # es.append(Edge(b-1, a-1, -cost))



if find_negative_loop(N, es): # cost < 0 の辺で行き来できる場合も負の閉路になる
  print('inf')
  print(1/0)
else:
  print(-bellman_ford(N, es,0)[N-1])

Submission status: Runtime Error

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

def bellman_ford(s):
    d = [float('inf')]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        if i == n - 1:
            inf_flg = d[-1]
            flg = True
    if flg:
        for i in range(n):
            update = False # 更新が行われたか
            for x, y, z in g:
                if d[y] > d[x] + z:
                    d[y] = d[x] + z
                    update = True
            if not update:
                break
            if i == n - 1:
                if inf_flg != d[-1]:
                    return "inf"
    return -1 * d[-1]

print(bellman_ford(0))

Submission status: Runtime Error

Solution code:
#ABC061D
from collections import deque
N,M = map(int,input().split())

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

def dfs(X,s):
    used = {s}
    search = deque([s])
    while search:
        ss = search.pop()
        for sss in X[ss]:
            if sss in used:
                continue
            used.add(sss)
            search.append(sss)
    return used

U = dfs(Adake,0) & dfs(Bdake,N-1)
ABC = [(a,b,c) for (a,b,c) in ABC if a in U and b in U]

INF = float('inf')
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for a,b,c in ABC:
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            if i==N-1 and b == N-1:
                print('inf')
                exit()
print(-dist[-1])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]

INF = float('inf')
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for a,b,c in ABC:
        a,b,c = a-1,b-1,-c
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            if i==N-1 and to == N-1:
                print('inf')
                exit()
print(-dist[-1])

Submission status: Runtime Error

Solution code:
N,M= map(int,input().split())
inf = 10**12 + 1
list=[[inf for i in range(N)] for j in range(N)]

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

flag = [inf for _ in range(N)]
value = -inf

def depth_search (now,tmp_flag,wage):
    global value
    tmp_flag[now] = wage
    for i in range(0,N):
        if(list[now][i] != inf):
            if(tmp_flag[i] != inf):
                if(tmp_flag[now] - tmp_flag[i] + list[now][i] > 0):
                    return inf
                else:
                    continue
            else:
                wage = wage + list[now][i]
                tmp_value = depth_search(i,tmp_flag,wage)
                if(tmp_value == inf):
                    return inf
                if(tmp_value > value):
                    value = tmp_value
    else:
        if(now == N-1):
            return wage
        else:
            return value

ans = depth_search(0,flag,0)
if(ans == inf):
    print("inf")
else:
    print(ans)

Submission status: Runtime Error

Solution code:
N,M= map(int,input().split())
list=[[0 for i in range(N)] for j in range(N)]

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

inf = 10**12 + 1
flag = [inf for _ in range(N)]
value = -inf

def depth_search (now,tmp_flag,wage):
    global value
    tmp_flag[now] = wage
    for i in range(0,N):
        if(list[now][i] != inf):
            if(tmp_flag[i] != inf):
                if(tmp_flag[now] - tmp_flag[i] + list[now][i] > 0):
                    return inf
                else:
                    continue
            else:
                wage = wage + list[now][i]
                tmp_value = depth_search(i,tmp_flag,wage)
                if(tmp_value == inf):
                    return inf
                if(tmp_value > value):
                    value = tmp_value
    else:
        if(now == N-1):
            return wage
        else:
            return value

ans = depth_search(0,flag,0)
if(ans == inf):
    print("inf")
else:
    print(ans)

Submission status: Runtime Error

Solution code:
N,M= map(int,input().split())
list=[[0 for i in range(N)] for j in range(N)]

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

inf = 10**12 + 1
flag = [0 for _ in range(N)]
value = -inf

def depth_search (now,tmp_flag,wage):
    global value
    tmp_flag[now] = wage
    for i in range(0,N):
        if(list[now][i] != 0):
            if(tmp_flag[i] != 0):
                if(tmp_flag[now] - tmp_flag[i] + list[now][i] > 0):
                    return inf
                else:
                    continue
            else:
                wage = wage + list[now][i]
                tmp_value = depth_search(i,tmp_flag,wage)
                if(tmp_value == inf):
                    return inf
                if(tmp_value > value):
                    value = tmp_value
    else:
        if(now == N-1):
            return wage
        else:
            return value

ans = depth_search(0,flag,0)
if(ans == inf):
    print("inf")
else:
    print(ans)

Submission status: Runtime Error

Solution code:
#ベルマンフォード法
#正の閉路がない時は普通のベルマンフォード法
n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n-1:
      memo=d[n-1]
    if cnt==n:
      #正のループがある
      if d[n-1]>memo:
        print(float("INF"))
        sys.exit()
      else:
        print(d[n])
  print(d[n-1])
  
Bellmanford(n,m,0,es)

Submission status: Runtime Error

Solution code:
from collections import deque

def fast_bellman_ford(n, s, graph, edge_n, init_val): #どう？
    d = [init_val] * n
    d[s] = 0
    q = deque([s])
    checker = [-1] * n
    for i in range(n):
        m = len(q)
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    if checker[vt] < i:
                        q.append(vt)
                        checker[vt] = i
        if not q:
            break
    if q: #閉路の存在
        minus_inf = -float('inf')
        i += 1
        while q:
            m = q.count
            for _ in range(m):
                vf = q.popleft()
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        if checker[vt] < i:
                            q.append(vt)
                            checker[vt] = i
            i += 1
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, 2 * m, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Submission status: Runtime Error

Solution code:
class FixedSizeQueue:
    def __init__(self, n, init_val):
        self.queue = [init_val] * n #根にサイズを負の値で格納する。
        self.l = 0
        self.r = 0
        self.n = n
        self.size = 0
    def append(self, val):
        if self.size == self.n:
            raise IndexError('fixed-size-queue is full')
        self.queue[self.r] = val
        self.r = (self.r + 1) % self.n
        self.size += 1

    def popleft(self):
        if self.size == 0:
            raise IndexError('dequeue from empty queue')
        val = self.queue[self.l]
        self.l = (self.l + 1) % self.n
        self.size -= 1
        return val

    def pop(self):
        if self.size == 0:
            raise IndexError('dequeue from empty queue')
        val = self.queue[self.r - 1]
        self.r = (self.r - 1) % self.n
        self.size -= 1
        return val
    
    def get_size(self):
        return self.size
    
    def __bool__(self):
        return self.size != 0

def fast_bellman_ford(n, s, graph, edge_n, init_val): #どう？
    d = [init_val] * n
    d[s] = 0
    q = FixedSizeQueue(edge_n, 0)
    q.append(s)
    for _ in range(n):
        m = q.get_size()
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    q.append(vt)
        if not q:
            break
    if q: #閉路の存在
        minus_inf = -float('inf')
        while q:
            m = q.get_size()
            for _ in range(m):
                vf = q.popleft()
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        q.append(vt)
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, 2 * m, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Submission status: Runtime Error

Solution code:
class FixedSizeQueue:
    def __init__(self, n, init_val):
        self.queue = [init_val] * n #根にサイズを負の値で格納する。
        self.l = 0
        self.r = 0
        self.n = n
        self.size = 0
    def append(self, val):
        if self.size == self.n:
            raise IndexError('fixed-size-queue is full')
        self.queue[self.r] = val
        self.r = (self.r + 1) % self.n
        self.size += 1

    def popleft(self):
        if self.size == 0:
            raise IndexError('dequeue from empty queue')
        val = self.queue[self.l]
        self.l = (self.l + 1) % self.n
        self.size -= 1
        return val

    def pop(self):
        if self.size == 0:
            raise IndexError('dequeue from empty queue')
        val = self.queue[self.r - 1]
        self.r = (self.r - 1) % self.n
        self.size -= 1
        return val
    
    def get_size(self):
        return self.size
    
    def __bool__(self):
        return self.size != 0

def fast_bellman_ford(n, s, graph, edge_n, init_val): #どう？
    d = [init_val] * n
    d[s] = 0
    q = FixedSizeQueue(edge_n, 0)
    q.append(s)
    for _ in range(n):
        m = q.get_size()
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    q.append(vt)
        if not q:
            break
    if q: #閉路の存在
        minus_inf = -float('inf')
        while q:
            m = q.get_size()
            for _ in range(m):
                vf = q.popleft()
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        q.append(vt)
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, m, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Submission status: Runtime Error

Solution code:
def moores_d(n, s, graph, init_val): 
    d = [init_val] * n
    d[s] = 0
    stack = [s]
    for _ in range(n):
        next_stack = []
        for _ in range(m):
            vf = stack.pop()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    next_stack.append(vt)
        stack = next_stack
        if not stack:
            break
    if stack: #閉路の存在
        minus_inf = -float('inf')
        next_stack = []
        while stack:
            vf = stack.pop()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = minus_inf
                    next_stack.append(vt)
            stack = next_stack
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = moores_d(n, 0, graph, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Submission status: Runtime Error

Solution code:
INF = 10**30
def bellman_ford(s, g):
    d = [INF for _ in range(n)] # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        # 負閉路が存在
        if i == n-1:
            return []
    return d

def connected_subgraph(s, g_pre):
  visited[s] = 1
  conn.add(s)
  for y in I[s]:
    if visited[y] == 0:
      connected_subgraph(y, g_pre)

n, m = map(int, input().split()) # n:頂点数, m:辺の数
g_pre = []
for _ in range(m):
    x, y, z = map(int, input().split()) # 始点,終点,コスト
    x -= 1
    y -= 1
    z *= -1
    g_pre.append([x, y, z])
    
I = [set() for _ in range(n)] #隣接グラフ
visited = [0 for _ in range(n)]
for x, y, z in g_pre:
  I[x].add(y)    
conn = set() 
connected_subgraph(0, g_pre)

g = []
for x, y, z in g_pre:
    if x in conn:
      g.append([x, y, z])
#print(conn, g)
ans = bellman_ford(0, g)
#print(ans)
print(-ans[n-1] if ans else "inf")

Submission status: Runtime Error

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

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

INF = 10 ** 40
S = [-INF] * N
S[0] = 0

def score(fst, s, C):
    for nx, p in R[fst]:
        if S[nx] >= s + p or S[nx] >= INF:
            continue
        S[nx] = s + p
        if nx in C:
            S[nx] = INF
        C[nx] = C.get(nx, 0) + 1
        score(nx, S[nx], C)
        C[nx] -= 1
        if C[nx] == 0:
            del C[nx]

score(0, 0, {0: 1})

if S[-1] < INF:
    ans = S[-1]
else:
    ans = "inf"

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
rl=sys.stdin.readline


def main():
    n,m=map(int,rl().strip().split())
    ewdata=[list(map(int,rl().strip().split())) for _ in range(m)]
    ew=dict(((x[0],x[1]),x[2]) for x in ewdata)
    ed=defaultdict(list)
    deg=defaultdict(int)
    memo=defaultdict(int)
    for x in ew:
        ed[x[0]].append(x[1])
        deg[x[0]]+=1
    prev=0
    curr=1
    scores=[0]*(n+2)
    cps=[0]*(n+1)
    maxscore=-10**14
    stack=[]
    c=1
    while memo[1]<deg[1]:
        if cps[curr]==0:
            cps[curr]=c
        else:
            if scores[c]-scores[cps[curr]]>0:
                maxscore='inf'
                break
            else:
                memo[prev]+=1
                curr=prev 
                prev=stack.pop()
                c-=1
                continue
        if curr==n:
            maxscore=max(scores[c],maxscore)
        if memo[curr]<deg[curr]:
            c+=1
            stack.append(prev)
            prev=curr
            curr=ed[curr][memo[curr]]
            scores[c]+=scores[c-1]+ew[(prev,curr)]
        else:
            scores[c]=0
            memo[curr]=0
            memo[prev]+=1
            cps[curr]=0
            cps[prev]=0
            curr=prev
            prev=stack.pop()
            c-=1
        # print(c,cps,stack)
        # print(c,cps,scores)
        # print(list(memo.items()),stack)
    # print(deg)
    print(maxscore)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)
n,m=map(int,input().split())
e=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  e[a-1].append((b-1,c))
def dfs1(now,vis):
  vis.append(now)
  if now==n-1:
    return 0
  res=-10**18
  for i,c in e[now]:
    if i not in vis:
      res=max(dfs1(i,vis[:])+c,res)
  return res

def dfs2(now,j,cnt):
  res=1
  if now==j and cnt:
    return 0
  cnt+=1
  for i,c in e[now]:
    res=dfs2(i,j,cnt)
  return res
vis=[]
ans=dfs1(0,vis)
frag=1
for i in vis:
  frag=min(frag,dfs2(i,i,0))
print(ans if frag else 'inf')

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
e=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  e[a-1].append((b-1,c))
def dfs1(now,vis):
  vis.append(now)
  if now==n-1:
    return 0
  res=-10**18
  for i,c in e[now]:
    if i not in vis:
      res=max(dfs1(i,vis[:])+c,res)
  return res

def dfs2(now,j,cnt):
  res=1
  if now==j and cnt:
    return 0
  cnt+=1
  for i,c in e[now]:
    res=dfs2(i,j,cnt)
  return res
vis=[]
ans=dfs1(0,vis)
frag=1
for i in vis:
  frag=min(frag,dfs2(i,i,0))
print(ans if frag else 'inf')

Submission status: Runtime Error

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

INF = 1 << 60
cost = [- INF] * (N + 1)
cost[1] = 0

for i in range(N):
    for n, nn, c in edge:
        if cost[nn] < cost[n] + c:
            # ワーシャルフロイド法の性質より、N回目に更新があるならinf
            if i == N - 1 and nn == N:
                print("inf")
                sys.exit()
            cost[nn] = cost[n] + c

print(cost[N])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

INF = 1 << 60

cost = [- INF] * (n + 1)
cost[1] = 0
for _ in range(n):
    visited = [[False] * (n + 1) for _ in range(n + 1)]
    q = deque([1])
    while q:
        curr = q.popleft()
        for d in graph[curr]:
            n, c = d[0], d[1]
            if visited[curr][n]:
                if cost[n] < cost[curr] + c:
                    print("inf")
                    sys.exit()
                else:
                    continue
            cost[n] = max(cost[n], cost[curr] + c)
            q.append(n)
            visited[curr][n] = True

print(cost[n])

Submission status: Runtime Error

Solution code:
#michatta ...
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path
import scipy
def main():
    N, M = map(int, input().split())
    p = []
    q = []
    w = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        p.append(a-1)
        q.append(b-1)
        w.append(-c)
    csr = csr_matrix((w, (p, q)), shape=(N, N))
    try:
        t = shortest_path(csr)
    except scipy.sparse.csgraph._shortest_path.NegativeCycleError:
        print('inf')
        return
    print(-int(t[0][-1]))
main()

Submission status: Runtime Error

Solution code:
#michatta ...
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path
import scipy
def main():
    N, M = map(int, input().split())
    p = []
    q = []
    w = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        p.append(a-1)
        q.append(b-1)
        w.append(-c)
    csr = csr_matrix((w, (p, q)), shape=(N, N))
    try:
        t = shortest_path(csr, indices=0)
    except scipy.sparse.csgraph._shortest_path.NegativeCycleError:
        print('inf')
        return
    print(-int(t[-1]))
main()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
    INF = 10 ** 40
    S = [-INF] * N
    S[0] = 0

    cur = set([0])
    def helper(n, s, hist):
        for g, gc in G[n]:
            if S[g] > s + gc or S[g] >= INF:
                continue
            S[g] = s + gc
            if g in hist:
                S[g] = INF
            hist.add(g)
            helper(g, S[g], hist)
            if g in hist:
                hist.remove(g)
    helper(0, 0, set())
    s = S[-1]
    return s if s < INF else 'inf'

print(main())

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse.csgraph._shortest_path import NegativeCycleError

input = sys.stdin.buffer.readline


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

graph = csr_matrix((costs, (starts, ends)), shape = (N, N))
try:
    ans = bellman_ford(graph, directed = True, indices = 0)[N-1]
    ans = int(round(-ans))
except NegativeCycleError:
    ans = "inf"
    
if ans == float("inf"):
    raise ValueError

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse.csgraph._shortest_path import NegativeCycleError

input = sys.stdin.buffer.readline


N, M = map(int, input().split())
starts = []
ends = []
costs = []
for _ in range(M):
    a, b, c = map(int, input().split())
    starts.append(a-1)
    ends.append(b-1)
    if c != 0:
        costs.append(-c)
    else:
        costs.append(sys.float_info.epsilon)

graph = csr_matrix((costs, (starts, ends)), shape = (N, N))
try:
    ans = bellman_ford(graph, directed = True, indices = 0)[N-1]
    ans = int(round(-ans))
except NegativeCycleError:
    ans = "inf"

print(ans)

Submission status: Runtime Error

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

cost = [-float('inf')]*N
cost[0] = 0

for i in range(2):
    for a,b,c in abc:
        a,b = a-1,b-1
            cost[b] = max(cost[b], cost[a] + c)
                
    if i == 0:
        ans = cost[N-1]
    else:
        Max = cost[N-1]


if ans != Max:
    print('inf')
else:
    print(ans)