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:
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        """
        graph : [[a1,b1,c1],[a2,b2,c2],‥]みたいな3次元配列のリスト,a1からb1までのコストはc1
        num_v :頂点の数
        start_point :スタート地点(a1)
        """
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point
 
 
    def execute(self):
        dist = [float("inf") for _ in range(self.num_v)]
        dist[self.start_point] = 0

        negative = [False for _ in range(self.num_v)]

        for i in range(self.num_v - 1):
            for start, end, cost in self.graph:
                if dist[end] > dist[start] + cost:
                    dist[end] = dist[start] + cost

        #負の経路がないなら|V-1|以上の繰り返しで最短経路の更新は行われない、負の経路の検出
        for i in range(self.num_v):
            for start, end, cost in self.graph:
                if dist[end] > dist[start] + cost:
                    dist[end] = dist[start] + cost
                    negative[end] = True
                if negative[start]:
                    negative[end] = True
        return dist, negative
 
N,M = map(int,input().split())
T = [[int(_) for _ in input().split()] for i in range(M)]

E = []
for a, b, c in T:
    E.append((a - 1, b - 1, c))

bellman = BellmanFord(graph, n, 0)
result, negative = bellman.execute()
 
if negative[-1]:
    print("inf")
else:
    print(-result[-1])

Submission status: Runtime Error

Solution code:
import math
V, E = [int(_) for _ in input().split()]
G = {}

for i in range(V):
    G[i] = {}
for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  # 0を始点とする場合
    t -= 1  # 0を始点とする場合
    G[s][t] = -c

INF = math.inf

D = [INF] * V
D[0] = 0  # 0を始点とする場合
count = 0
while True:
    count += 1
    update = False
    for s in G.keys():
        for t in G[s].keys():
            if D[s] != INF and D[t] > D[s] + G[s][t]:
                D[t] = D[s] + G[s][t]
                update = True
    if not update:
        break
    if count == V:
        print('inf')
        exit()
print(-D[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

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


score = [inf for _ in range(n)]
def dfs(v):
    for u in range(n):
        if edge[v][u]<inf:
            if score[u]<inf:
                if score[v]+edge[v][u]>score[u]:
                    print("inf")
                    exit()
            else:
                score[u] = score[v] + edge[v][u]
                dfs(u)

score[0] = 0
dfs(0)
print(score[n-1])

Submission status: Runtime Error

Solution code:
#061-D
#v,Eは、頂点(vertex),辺(edge)の数
v,E=map(int,input().split())
e=[]
for i in range(E): #eの各要素は[始点,終点,コスト]
    f,t,c=map(int,input().split())
    e.append([f-1,t-1,-c])
d=[None for i in range(v)]
def lp(s,g): #sは始点、dに各頂点への最短距離が格納される
    for i in range(v):
        d[i]=float('INF')
    d[s]=0
    c=0
    while c<v+1:
        update=False
        for i in range(E):
            if d[e[i][0]]!=float('INF') and d[e[i][1]]>d[e[i][0]]+e[i][2]:
                d[e[i][1]]=d[e[i][0]]+e[i][2]
                update=True
        if update==False:
            break
        c+=1
    if c==v+1:
        print('inf')
    else:
        print(-d[g])
lp(0,2)

Submission status: Runtime Error

Solution code:
#061-D
#v,Eは、頂点(vertex),辺(edge)の数
v,E=map(int,input().split())
e=[]
for i in range(E): #eの各要素は[始点,終点,コスト]
    f,t,c=map(int,input().split())
    e.append([f-1,t-1,-c])
d=[None for i in range(v)]
def lp(s,g): #sは始点、dに各頂点への最短距離が格納される
    for i in range(v):
        d[i]=float('INF')
    d[s]=0
    c=0
    while c<v+1:
        update=False
        for i in range(E):
            if d[e[i][0]]!=float('INF') and d[e[i][1]]>d[e[i][0]]+e[i][2]:
                d[e[i][1]]=d[e[i][0]]+e[i][2]
                update=True
        if update==False:
            break
    if c==v+1:
        print('inf')
    else:
        print(-d[g])
lp(0,2)

Submission status: Runtime Error

Solution code:

import queue

class Graph:

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

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

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

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


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

G = Graph(N,True)

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

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

Submission status: Runtime Error

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

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

for i in range(N-1):
    update = False
    for na, nb, nc in path:
        if score[na] != -inf and score[nb] < score[na] + nc:
            score[nb] = score[na]+nc
            update = True
    if not update:
        break
ans = score[N-1]
for na, nb, nc in path:
        if score[na] != -inf and score[nb] < score[na] + nc:
            score[nb] = score[na]+nc
print(ans if ans == score[N-1] else 'inf')

Submission status: Runtime Error

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

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

if loop:
    print('inf')
else:
    print(-ans)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
inf = int(1e20)
node,edge = map(int,input().split())
ed = []
for e in range(edge):
    ed.append(e[0]-1,e[1]-1,-e[2])
start = 0
goal = node-1



d = [inf for i in range(node)]
pre = [inf for i in range(node)]
d[start] = 0

for i in range(node):
    update = False
    for e in ed:
        if d[e[0]] != inf and d[e[1]]>d[e[0]]+e[2]:
            d[e[1]] = d[e[0]]+e[2]
            update = True
            pre[e[1]] = e[0]
    if update==False:
        print(-d[goal])
        break
else:
    nowcos = d[goal]
    for i in range(node):
        for e in ed:
            if d[e[0]] != inf and d[e[1]]>d[e[0]]+e[2]:
                d[e[1]] = d[e[0]]+e[2]
                pre[e[1]] = e[0]
    if nowcos != d[goal]:
        print('inf')
    else:
        print(-d[goal])

Submission status: Runtime Error

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

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

import networkx as nx
G = nx.DiGraph()
G.add_weighted_edges_from(edge)
if nx.negative_edge_cycle(G):
    print('inf')
else:
    print(-nx.bellman_ford_path_length(G, source=0, target=n-1))

Submission status: Runtime Error

Solution code:
INF = float('inf')
N,M = map(int,input().split())
edge = []
d = [INF]*N
d[0] = 0
negative = [False for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,-c])

for i in range(N):
    for j in range(M):
        if d[edge[j][0]]==INF:
            continue
        d[edge[j][1]] = min(d[edge[j][1]],d[edge[j][0]]+edge[j][2])

ans = d[N-1]

for i in range(N):
    for j in range(M):
        if d[j]==INF:
            continue
        if d[edge[j][1]]>d[edge[j][0]]+edge[j][2]:
            d[edge[j][1]]=d[edge[j][0]]+edge[j][2]
            negative[edge[j][1]] = True
        if negative[edge[j][0]]:
            negative[edge[j][1]] = True
print('inf' if negative[N-1] else -ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
inf = 10**50
n,m = map(int, input().split())

ea = []
eb = []
cost = []

for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    ea.append(a)
    eb.append(b)
    cost.append(-c)

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    update = False
    for i in range(m):
        a = ea[i]
        b = eb[i]
        c = cost[i]
        if d[a]!=inf and d[b]>d[a]+c:
            d[b] = d[a]+c
            update = True
    if not update:
        break

ans = d[n-1]
negative = [False for _ in range(n)]
for _ in range(n):
    update = False
    for i in range(m):
        a = ea[i]
        b = eb[i]
        c = cost[i]
        if d[a]!=inf and d[b]>d[a]+c:
            d[b] = d[a]+c
            negative[b] = True
            update = True
        if negative[a]:
            negative[b] = True
            update = True
    if no update:
        break
# print(d)
if negative[n-1]:
    print("inf")
else:
    print(-ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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


class Graph(object):
    def __init__(self):
        self.edges = defaultdict(list)
        self.nodes = set()

    def add_edge(self, src, dst, weight=1):
        self.edges[src].append((dst, weight))
        self.nodes.add(src)
        self.nodes.add(dst)


def bellman_ford(graph, start):
    N = len(graph.nodes)
    dist = [int(1e18)] * N
    dist[start] = 0
    prev = [None] * N

    for _ in range(N - 1):
        for u, l in graph.edges.items():
            for v, weight in l:
                if dist[v] > dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
    
    for u, l in graph.edges.items():
        for v, weight in l:
             if dist[u] + weight < dist[v]:
                 return False
    return dist


g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, -c)

dist = bellman_ford(g, 0)
if dist:
    print(-dist[N - 1])
else:
    print('inf')

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

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


class Graph(object):
    def __init__(self):
        self.edges = defaultdict(list)
        self.nodes = set()

    def add_edge(self, src, dst, weight=1):
        self.edges[src].append((dst, weight))
        self.nodes.add(src)
        self.nodes.add(dst)


def BellmanFord(graph, start):
    N = len(graph.nodes)
    dist = [float('inf')] * N
    dist[start] = 0
    prev = [None] * N

    for _ in range(N - 1):
        for u, l in graph.edges.items():
            for v, weight in l:
                if dist[v] > dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
    
    for u, l in graph.edges.items():
        for v, weight in l:
             if dist[u] + weight < dist[v]:
                 return False
    return dist


g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, -c)

dist = BellmanFord(g, 0)
if dist:
    print(-dist[N - 1])
else:
    print('inf')

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

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


class Graph(object):
    def __init__(self):
        self.edges = defaultdict(list)
        self.nodes = set()

    def add_edge(self, src, dst, weight=1):
        self.edges[src].append((dst, weight))
        self.nodes.add(src)
        self.nodes.add(dst)


def BellmanFord(graph, start):
    N = len(graph.nodes)
    dist = [float('-inf')] * N
    dist[start] = 0
    prev = [None] * N

    for _ in range(N - 1):
        for u, l in graph.edges.items():
            for v, weight in l:
                if dist[v] < dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
    
    for u, l in graph.edges.items():
        for v, weight in l:
             if dist[u] + weight > dist[v]:
                 return False
    return dist


g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, c)

dist = BellmanFord(g, 0)
if dist:
    print(dist[N - 1])
else:
    print('inf')

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

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


class Graph(object):
    def __init__(self):
        self.edges = defaultdict(list)
        self.nodes = set()

    def add_edge(self, src, dst, weight=1):
        self.edges[src].append((dst, weight))
        self.nodes.add(src)
        self.nodes.add(dst)


def BellmanFord(graph, start):
    N = len(graph.nodes)
    dist = [float('-inf')] * N
    dist[start] = 0
    prev = [None] * N

    for _ in range(N):
        for u, l in graph.edges.items():
            for v, weight in l:
                if dist[v] < dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
    
    for u, l in graph.edges.items():
        for v, weight in l:
             if dist[u] + weight > dist[v]:
                 return False
    return dist


def topological_sort(graph):
    g = graph.edges
    N = len(graph.nodes)

    indeg = [0] * N
    for v in g:
        for u, _ in g[v]:
            indeg[u] += 1

    S = [i for i in range(N) if indeg[i] == 0]
    L = []

    while S:
        u = S.pop()
        L.append(u)
        for v, _ in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                S.append(v)
    return L


g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, c)

if len(topological_sort(g)) == N:
    dist = BellmanFord(g, 0)
    if dist:
        print(dist[N - 1])
    else:
        print('inf')
else:
    print('inf')

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

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


class Graph(object):
    def __init__(self):
        self.edges = defaultdict(list)
        self.nodes = set()

    def add_edge(self, src, dst, weight=1):
        self.edges[src].append((dst, weight))
        self.nodes.add(src)
        self.nodes.add(dst)


def BellmanFord(graph, start):
    N = len(graph.nodes)
    dist = [float('-inf')] * N
    dist[start] = 0
    prev = [None] * N

    for _ in range(N):
        for u, l in graph.edges.items():
            for v, weight in l:
                if dist[v] < dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
    return dist


def topological_sort(graph):
    g = graph.edges
    N = len(graph.nodes)

    indeg = [0] * N
    for v in g:
        for u, _ in g[v]:
            indeg[u] += 1

    S = [i for i in range(N) if indeg[i] == 0]
    L = []

    while S:
        u = S.pop()
        L.append(u)
        for v, _ in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                S.append(v)
    return L


g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, c)

if len(topological_sort(g)) == N:
    dist = BellmanFord(g, 0)
    print(dist[N - 1])
else:
    print('inf')

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

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


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)
        self.nodes = set()

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))
        self.nodes.add(src)
        self.nodes.add(dst)

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('-inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] > dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] < alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]


def topological_sort(graph):
    g = graph.graph
    N = len(graph.nodes)

    indeg = [0] * N
    for v in g:
        for u, _ in g[v]:
            indeg[u] += 1

    S = [i for i in range(N) if indeg[i] == 0]
    L = []

    while S:
        u = S.pop()
        L.append(u)
        for v, _ in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                S.append(v)
    return L


g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, c)

if len(topological_sort(g)) == N:
    d = Dijkstra(g, 0)
    print(d.shortest_distance(N - 1))
else:
    print('inf')

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a,b,c=[None]*n,[None]*n,[None]*n
inf=float("inf")
d=[inf]*n
neg=[False]*n
d[0]=0

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

for loop 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]

for loop 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]
      neg[b[i]-1]=True
    if neg[a[i]-1]:
      neg[b[i]-1]=True

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

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop
n,m=map(int,input().split())
a,b,c=[None]*n,[None]*n,[None]*n
inf=float("inf")
d=[inf]*n

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

d[0]=0
for loop 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]
neg=[False]*n
for loop 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]
      neg[b[i]-1]=True
    if neg[a[i]-1]:
      neg[b[i]-1]=True

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

Submission status: Runtime Error

Solution code:
from math import inf
n, m = list(map(int, input().split()))
a, b, c = [], [], []
for _ in range(m):
    abc = list(map(int, input().split()))
    a.append(abc[0])
    b.append(abc[1])
    c.append(-abc[2]) # convert pos-neg

dist = [inf]*(n+1)
dist[1] = 0
for loop in range(n-1):
    for i in range(m):
        if dist[a[i]] == inf:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
ans = dist[-1]

negative = [False]*(n+1) # negative closed path
for loop in range(n):
    for i in range(m):
        if dist[a[i]] == inf:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
            negative[b[i]] = True
        if negative[a[i]] is True:
            negative[b[i]] = True

# print(dist, negative)
if negative[-1] is True:
    print('inf')
else:
    print(-ans)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
paths = {}
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in paths.keys():
        paths[a] = {b:c}
    else:
        paths[a][b] = c
# print(paths)

score = [None]*(n+1)
score[1] = 0
stack = [(k, [1]) for k in paths[1].keys()]
is_inf = False
while len(stack) > 0 and not is_inf:
    node, path = stack[-1]
    node_before = path[-1]
    stack = stack[:-1]
    if score[node] is None:
        score[node] = score[node_before] + paths[node_before][node]
    elif score[node_before] + paths[node_before][node] > score[node]:
        score[node] = score[node_before] + paths[node_before][node]
    else:
        continue

    if node == n and not n in paths.keys():
        continue

    for node_next in paths[node].keys():
        if node_next in path:
            is_inf = True
            break
        else:
            stack.append((node_next, path+[node]))
    # print(stack, score)

if is_inf:
    print('inf')
else:
    print(score[-1])

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-1,b-1, c))
point = [None] * N
point[0] = 0
for i in range(N):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
current_point = point[N-1]
for a,b,c in edge:
    if point[a] is not None:
        if point[b] is None:
            point[b] = point[a] + c
    point[b] = max(point[b], point[a] + c)
if current_point < point[N-1]:
    print("inf")
else:
    print(current_point)

Submission status: Runtime Error

Solution code:
from math import inf

N, M = map(int, input().split())
edges = []
for j in range(M):
    edges.append(list(map(int, input().split())))

d = [0] + ([-inf]*(N-1))
pred = [None] * N

for i in range(N-1):
    for j in range(M):
        u = edges[j][0]-1
        v = edges[j][1]-1
        w = edges[j][2]
        if d[v] < d[u] + w:
            d[v] = d[u] + w
            pred[v] = u

positive_loop = False
for j in range(M):
    u = edges[j][0]-1
    v = edges[j][1]-1
    w = edges[j][2]
    if d[u] + w > d[v]:
        positive_loop = True

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

Submission status: Runtime Error

Solution code:
import sys

INF = float('inf')

def Bellmanford(n, edges, r): #r: 始点
    d = [INF] * n
    d[r] = 0
    
    for i in range(n):
        flag = False
        
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                flag = True
        
        if flag and i == n-1 and t == n-1:
            return 'inf'
    
    return -d[n-1]
    

N, M = map(int, sys.stdin.readline().split())
Edges = [None] * M

for i in range(M):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    Edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(N, Edges, 0)

print(ans)

Submission status: Runtime Error

Solution code:
import sys 

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

for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)
    c_list.append(-c)

inf = sys.maxsize
dist = [inf for _ in range(N)]
dist[0] = 0

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

ans = dist[N-1]
negative = [False for _ in range(N)]

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

if nagative[N-1]:
    print('inf')
else:
    print(str(-ans))

Submission status: Runtime Error

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

for i in range(M):
    a, b, c = map(int, input().split())
    v= tree.get(a,[])
    v.append([b, c])
    tree[a] = v

m = []
def cost(v, c, visited):
    if v in visited:
        m.append(c)
        if max(m) > 0:
            print('inf')
            exit()
        return
    b = tree.get(v, None)
    if b is None:
        m.append(c)
        return 
    elif len(b) == 1 and tree.get(b[0][0],None) == None:
        j = c+b[0][1]
        m.append(j)
    else:
        for b, c2 in b: 
            cost(b, c+c2, visited + [v])

cost(1, 0, [])
print(max(m))

Submission status: Runtime Error

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

for i in range(M):
    a, b, c = map(int, input().split())
    v= tree.get(a,[])
    v.append([b, c])
    tree[a] = v

def has_loop(tree):
    pass

m = []
def cost(v, c, visited):
    if v in visited:
        m.append(c)
        if max(m) <= 0:
            print(max(m))
        else:
            print('inf')
        exit()
    b = tree.get(v, None)
    if b is None:
        return 
    elif len(b) == 1 and tree.get(b[0][0],None) == None:
        j = c+b[0][1]
        m.append(j)
    else:
        for b, c2 in b: 
            cost(b, c+c2, visited + [v])

if has_loop(tree):
    print('inf')
    exit()

cost(1, 0, [])
print(max(m))

Submission status: Runtime Error

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

for i in range(M):
    a, b, c = map(int, input().split())
    v= tree.get(a,[])
    v.append([b, c])
    tree[a] = v

def has_loop(tree):
    pass

m = []
def cost(v, c, visited):
    if v in visited:
        m.append(c)
        if max(m) < 0:
            print(max(m))
        else:
            print('inf')
        exit()
    b = tree.get(v, None)
    if b is None:
        return 
    elif len(b) == 1 and tree.get(b[0][0],None) == None:
        j = c+b[0][1]
        m.append(j)
    else:
        for b, c2 in b: 
            cost(b, c+c2, visited + [v])

if has_loop(tree):
    print('inf')
    exit()

cost(1, 0, [])
print(max(m))

Submission status: Runtime Error

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

for i in range(M):
    a, b, c = map(int, input().split())
    v= tree.get(a,[])
    v.append([b, c])
    tree[a] = v

def has_loop(tree):
    pass

m = []
def cost(v, c, visited):
    if v in visited:
        if max(m) < 0:
            print(max(m))
        else:
            print('inf')
        exit()
    b = tree.get(v, None)
    if b is None:
        return 
    elif len(b) == 1 and tree.get(b[0][0],None) == None:
        j = c+b[0][1]
        m.append(j)
    else:
        for b, c2 in b: 
            cost(b, c+c2, visited + [v])

if has_loop(tree):
    print('inf')
    exit()

cost(1, 0, [])
print(max(m))