Problem:


Score : 400 points

Problem Statement

There is a directed graph with N vertices and M edges.
The i-th edge (1≤i≤M) points from vertex a_i to vertex b_i, and has a weight c_i.
We will play the following single-player game using this graph and a piece.

Initially, the piece is placed at vertex 1, and the score of the player is set to 0.
The player can move the piece as follows:

When the piece is placed at vertex a_i, move the piece along the i-th edge to vertex b_i. After this move, the score of the player is increased by c_i.

The player can end the game only when the piece is placed at vertex N.
The given graph guarantees that it is possible to traverse from vertex 1 to vertex N.

When the player acts optimally to maximize the score at the end of the game, what will the score be?
If it is possible to increase the score indefinitely, print inf.

Constraints

2≤N≤1000 

1≤M≤min(N(N-1),2000) 

1≤a_i,b_i≤N (1≤i≤M) 

a_i≠b_i (1≤i≤M) 

a_i≠a_j or b_i≠b_j (1≤i<j≤M) 

-10^9≤c_i≤10^9 (1≤i≤M)

c_i is an integer.

In the given graph, there exists a path from vertex 1 to vertex N.

Input

Input is given from Standard Input in the following format:  

N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

Output

Print the maximum possible score at the end of the game, if it is finite. If it is possible to increase the score indefinitely, print inf.  

Sample Input 1

3 3
1 2 4
2 3 3
1 3 5

Sample Output 1

7

There are two ways to move the piece to vertex N=3:

vertex 1 → vertex 2 → vertex 3 : score 4+3=7

vertex 1 → vertex 3 : score 5

Thus, the maximum possible score at the end of the game is 7.

Sample Input 2

2 2
1 2 1
2 1 1

Sample Output 2

inf

It is possible to increase the score indefinitely by alternating between vertex 1 and 2.

Sample Input 3

6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000

Sample Output 3

-5000000000



Sample input:
3 3
1 2 4
2 3 3
1 3 5


Sample output:
7

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def SPFA(N, G, s):
    dist = [INF] * N
    cont = [0] * N
    cnts = [0]* N

    dist[s] = 0
    cont[s] = 1
    cnts[s] += 1
    que = deque([s])
    su = s; num = 1
    while que:
        v = que.popleft()
        cont[v] = 0
        d = dist[v]
        su -= d
        num -= 1
        for w, c in G[v]:
            r = d + c
            if r < dist[w]:
                if not cont[w]:
                    cnts[w] += 1
                    if N <= cnts[w]:
                        return None
                    if que and r < que[0]:
                        que.appendleft(w)
                    else:
                        que.append(w)
                    cont[w] = 1
                    su += r
                    num += 1
                    dist[w] = r
                    while su < dist[que[0]]*num:
                        que.append(que.popleft())
                else:
                    su += r - dist[w]
                    dist[w] = r
    return dist

class BellmanFord:
    INF = int(1e18)
    N = -1
    edge = []
    def __init__(self, N):
        self.N = N
    def add_edge(self, frm, to, cost):
        self.edge.append((frm, to, cost));
    def add_bi_edge(self, a, b, cost):
        self.add_edge(a, b, cost)
        self.add_edge(b, a, cost)
    def calcD(self, start):
        D = [self.INF] * self.N
        D[start] = 0
        update, cnt = True, 0
        while update:
            update = False
            cnt = cnt + 1
            if cnt >= self.N:
                return None
            for frm, to, cost in self.edge:
                ncost = D[frm] + cost
                if D[frm] == self.INF or ncost >= D[to]:
                    continue
                D[to] = ncost
                update = True
        return D

N, M = MAP()
abc = [LIST() for _ in range(M)]
G = [[] for _ in range(N)]

bf = BellmanFord(N)
for a, b, c in abc:
	bf.add_edge(a-1, b-1, -c)
# for a, b, c in abc:
# 	G[a-1].append((b-1, -c))
ans = bf.calcD(0)
if not ans:
	print("inf")
else:
	print(-ans[N-1])
# dist = SPFA(N, G, 0)
# if dist is None:
#     print("inf")
# else:
#     print(-dist[N-1])

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def SPFA(N, G, s):
    dist = [INF] * N
    cont = [0] * N
    cnts = [0]* N

    dist[s] = 0
    cont[s] = 1
    cnts[s] += 1
    que = deque([s])
    su = s; num = 1
    while que:
        v = que.popleft()
        cont[v] = 0
        d = dist[v]
        su -= d
        num -= 1
        for w, c in G[v]:
            r = d + c
            if r < dist[w]:
                if not cont[w]:
                    cnts[w] += 1
                    if N <= cnts[w]:
                        return None
                    if que and r < que[0]:
                        que.appendleft(w)
                    else:
                        que.append(w)
                    cont[w] = 1
                    su += r
                    num += 1
                    dist[w] = r
                    while su < dist[que[0]]*num:
                        que.append(que.popleft())
                else:
                    su += r - dist[w]
                    dist[w] = r
    return dist

class BellmanFord:
    INF = int(1e18)
    N = -1
    edge = []
    def __init__(self, N):
        self.N = N
    def add_edge(self, frm, to, cost):
        self.edge.append((frm, to, cost));
    def add_bi_edge(self, a, b, cost):
        self.add_edge(a, b, cost)
        self.add_edge(b, a, cost)
    def calcD(self, start):
        D = [self.INF] * self.N
        D[start] = 0
        update, cnt = True, 0
        while update:
            update = False
            cnt = cnt + 1
            if cnt > self.N:
                return None
            for frm, to, cost in self.edge:
                ncost = D[frm] + cost
                if D[frm] == self.INF or ncost >= D[to]:
                    continue
                D[to] = ncost
                update = True
        return D

N, M = MAP()
abc = [LIST() for _ in range(M)]
G = [[] for _ in range(N)]

bf = BellmanFord(N)
for a, b, c in abc:
	bf.add_edge(a-1, b-1, -c)
# for a, b, c in abc:
# 	G[a-1].append((b-1, -c))
ans = bf.calcD(0)
if not ans:
	print("inf")
else:
	print(-ans[N-1])
# dist = SPFA(N, G, 0)
# if dist is None:
#     print("inf")
# else:
#     print(-dist[N-1])

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def SPFA(N, G, s):
    dist = [INF] * N
    cont = [0] * N
    cnts = [0]* N

    dist[s] = 0
    cont[s] = 1
    cnts[s] += 1
    que = deque([s])
    su = s; num = 1
    while que:
        v = que.popleft()
        cont[v] = 0
        d = dist[v]
        su -= d
        num -= 1
        for w, c in G[v]:
            r = d + c
            if r < dist[w]:
                if not cont[w]:
                    cnts[w] += 1
                    if N <= cnts[w]:
                        return None
                    if que and r < que[0]:
                        que.appendleft(w)
                    else:
                        que.append(w)
                    cont[w] = 1
                    su += r
                    num += 1
                    dist[w] = r
                    while su < dist[que[0]]*num:
                        que.append(que.popleft())
                else:
                    su += r - dist[w]
                    dist[w] = r
    return dist

N, M = MAP()
abc = [LIST() for _ in range(M)]
G = [[] for _ in range(N)]

for a, b, c in abc:
	G[a-1].append((b-1, -c))

dist = SPFA(N, G, 0)
if dist is None:
    print("inf")
else:
    print(-dist[N-1])

Submission status: Wrong Answer

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

def find_negative_loop(v,e,es):
    # v:頂点数　e:辺の数　es:[[s,t,c]]
    d = [float("inf")]*v
    d[0]=0
    for i in range(v):
        for j in range(e):
            x=es[j]
            if d[x[1]] > d[x[0]] + x[2]:
                d[x[1]] = d[x[0]]+ x[2]
                if i == v-1:
                    return True
    return False

if find_negative_loop(n,m,es):
    print("inf")
    exit()

def bellman_ford(s,v,e,es):
    #s:始点　v:頂点数　e:辺の数　es:[s,t,c]
    d = [float("inf")]*v
    d[s] = 0

    while True:
        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
        if not update:
            break

    return d

d=bellman_ford(0,n,m,es)
print(-d[n-1])

Submission status: Wrong Answer

Solution code:
inf = float('inf')
# ベルマンフォード法
# 計算量O(VE) V:頂点数, E:辺の数
# [引数]   n:頂点数, edges:辺集合, start:始点, end:終点
# [返り値] dist:startからの最短距離, exists_negative_cycle: 負閉路が存在するかどうか
def bellmanford(n : int, edges : list, start : int, goal : int) -> (list, bool):
    dist = [inf] * n
    dist[start] = 0
    exist_negative_cycle = True

    # 負閉路を含まないとき、頂点数nなら更新は高々n-1回で済む
    for _ in range(N-1):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w


    # (1)グラフに負閉路が含まれるときの検出
    # N回目で更新があったとき、グラフは負閉路を含む
    # for v, nv, w in edges:
    #     if dist[nv] > dist[v] + w:
    #         is_cycle = False

    # (2)startとendのパスに負閉路が含まれるときの検出
    is_updated = [False] * n
    for _ in range(N):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                is_updated[b] = True
            if is_updated[v] is True:
                is_updated[nv] = True

    exist_negative_cycle = is_updated[goal]

    return dist, exist_negative_cycle

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

dist, exist_negative_cycle = bellmanford(N, edges, 0, N-1)

if exist_negative_cycle is True:
    ans = "inf"
else:
    ans = -dist[N-1]

print(ans)

Submission status: Wrong Answer

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

inf = float('inf')
# 計算量O(VE) V:頂点数, E:辺の数
# True - >正常に更新, False -> startからendまでの経路において負閉路有り
def bellmanford(start, end):
    global dist
    dist = [inf] * N
    dist[start] = 0
    # 頂点数Nなら更新は高々N-1回で済む
    for _ in range(N-1):
        for v ,nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
    # 負閉路の検出部分
    # N回目で更新があった場合、負閉路を含む
    for v, nv, w in edges:
        if dist[nv] > dist[v] + w:
            return False
    return True

flag = bellmanford(0, N-1)
if flag is False:
    print("inf")
    exit()

ans = -dist[N-1]
print(ans)

Submission status: Wrong Answer

Solution code:
# ABC061d
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def BellmanFord(edges, num_v, source):
      # グラフの初期化
    inf = float("inf")
    dist = [inf for i in range(num_v)]
    dist[source-1] = 0

    # 辺の緩和
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i == num_v-1:
                    return -1

    return dist


n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, -c))
ans = BellmanFord(edges, n, 1)
print(-ans[n-1] if ans != -1 else 'inf')

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
graph = csr_matrix((-edge[2], (edge[:2] - 1)), (N, N))

try:
  	# start、goalが決まっているので,'indices=[0]'を指定
    # directed=True:有効グラフ
    dist = bellman_ford(graph, indices=[0])
except Exception: # 全ての例外をキャッチ
    print("inf")
else:    
  print(int(-(dist[0][-1])))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
INF = (10**18+1)
graph = [[INF]*N for _ in range(N)]
for _ in range(M):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  graph[a][b] = -c

csr = csr_matrix(graph)
  
try:
  	# start、goalが決まっているので,'indices=[0]'を指定
    # directed=True:有効グラフ
    dist = bellman_ford(csr, indices=[0])
except Exception: # 全ての例外をキャッチ
    print("inf")
else:    
  print(int(-(dist[0][-1])))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
INF = N*(10**9+1)
graph = [[INF]*N for _ in range(N)]
for _ in range(M):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  graph[a][b] = -c

csr = csr_matrix(graph)
  
try:
  	# start、goalが決まっているので,'indices=[0]'を指定
    # directed=True:有効グラフ
    dist = bellman_ford(csr, indices=[0])
except Exception: # 全ての例外をキャッチ
    print("inf")
else:    
  print(int(-(dist[0][-1])))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

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

csr = csr_matrix(graph)
  
try:
  	# start、goalが決まっているので,'indices=[0]'を指定
    # directed=True:有効グラフ
    dist = bellman_ford(csr, indices=[0])
except Exception: # 全ての例外をキャッチ
    print("inf")
else:    
  print(int(-(dist[0][-1])))

Submission status: Wrong Answer

Solution code:
def bellman_ford(n, edges, s):
    d = [float('inf')] * n
    d[s] = 0
    
    loop_cnt = 0
    while True:
        loop_cnt += 1
        update = False
        for i in range(len(edges)):
            e = edges[i]
            if d[e[0]] != float('inf') and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        
        if not update or loop_cnt >= n: break
    return d, (loop_cnt >= n)

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

dist, cycle = bellman_ford(n, edges, 0)
if cycle:
    print("inf")
else :
    print(-dist[n-1])

Submission status: Wrong Answer

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 BellmanFord(E, N, source):
    #E:E[a]は頂点aを始点とする辺のリストであり、辺の終点bと辺の重みwが(b, w)の形で格納されている
    #N:頂点の数
    #source:始点
    #グラフの初期化
    inf = 10**20
    d = [inf for _ in range(N)]
    d[source] = 0
    
    #辺の緩和
    for i in range(N):
        for j in range(N):
            e = E[j]
            if len(e) == 0:
                continue
            for edge in e:
                if d[edge[0]] > d[j] + edge[1]:
                    d[edge[0]] = d[j] + edge[1]
                    if i == N-1 and j == N-1: return -1
    
    return d

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

Submission status: Wrong Answer

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 BellmanFord(E, N, source):
    #E:E[a]は頂点aを始点とする辺のリストであり、辺の終点bと辺の重みwが(b, w)の形で格納されている
    #N:頂点の数
    #source:始点
    #グラフの初期化
    inf = 10**15
    d = [inf for _ in range(N)]
    d[source] = 0
    
    #辺の緩和
    for i in range(N):
        for j in range(N):
            e = E[j]
            if len(e) == 0:
                continue
            for edge in e:
                if d[edge[0]] > d[j] + edge[1]:
                    d[edge[0]] = d[j] + edge[1]
                    if i == N-1 and j == N-1: return -1
    
    return d

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

Submission status: Wrong Answer

Solution code:
INF = 10**18

N,M = map(int,input().split())
edge = [list(map(int,input().split())) for i in range(M)]

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

for e in edge:
    graph[e[0]-1].append([e[1]-1,-e[2]])
    
dist = [INF for _ in range(N)]
dist[0] = 0

for _ in range(N):
    flag = False
    for node,g in enumerate(graph):
        for adj,cost in g:
            if dist[node] != INF and dist[node]+cost < dist[adj]:
                dist[adj] = dist[node]+cost
                flag = True
    if not flag:
        print(-dist[N-1])
        break
else:
    print('inf')

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, bellman_ford
mINF = -(10**16)
n,m = map(int,input().split())
A = [0]*m
B = [0]*m
C = [0]*m
for i in range(m) :
    a, b, c = map(int,input().split())
    A[i], B[i], C[i] = a-1, b-1, -c

graph = [[mINF]*n for i in range(n)]
for i in range(m) :
    graph[A[i]][B[i]] = C[i]

graph = csgraph_from_dense(graph, null_value=mINF)
try :
    dist = bellman_ford(graph).astype(int)
    ans = (-dist[0][n-1])
except : # NegativeCycleError in scipy
    ans = "inf"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

n,m = map(int,input().split())
A = [0]*m
B = [0]*m
C = [0]*m
for i in range(m) :
    a, b, c = map(int,input().split())
    A[i], B[i], C[i] = a-1, b-1, -c

mINF = -(10**16)
graph = [[mINF]*n for i in range(n)]
for i in range(m) :
    graph[A[i]][B[i]] = C[i]

graph = csgraph_from_dense(graph, null_value=mINF)

try :
    dist = floyd_warshall(graph).astype(int)
    ans = -dist[0][n-1]
except : # NegativeCycleError in scipy
    ans = "inf"

print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

n,m = map(int,input().split())
A = [0]*m
B = [0]*m
C = [0]*m
for i in range(m) :
    a, b, c = map(int,input().split())
    A[i], B[i], C[i] = a-1, b-1, -c

mINF = -10**9
graph = [[mINF]*n for i in range(n)]
for i in range(m) :
    graph[A[i]][B[i]] = C[i]

graph = csgraph_from_dense(graph, null_value=mINF)

try :
    dist = floyd_warshall(graph).astype(int)
    ans = -dist[0][n-1]
except : # NegativeCycleError in scipy
    ans = "inf"

print(ans)

Submission status: Wrong Answer

Solution code:
def bellman_ford(edges, num_v, start):
    """
    ベルマンフォード法
    :param edges: (from, to, cost)のリスト
    :param num_v: 頂点の数
    :param start: 始点
    :return: それぞれの頂点の最小コスト
    """
    inf = float("inf")
    result = [inf] * num_v
    result[start - 1] = 0

    for i in range(num_v):
        for edge in edges:
            if result[edge[1] - 1] > result[edge[0] - 1] + edge[2]:
                result[edge[1] - 1] = result[edge[0] - 1] + edge[2]
                if i == num_v - 1:
                    return -1

    return result


def abc061_d():
    n, m = map(int, input().split())
    edges = []
    for _ in range(m):
        *v, = map(int, input().split())
        edges.append((v[0], v[1], -v[2]))

    result = bellman_ford(edges, n, 1)
    if result == -1:
        print("inf")
    else:
        print(-result[n - 1])

if __name__ == '__main__':
    abc061_d()

Submission status: Wrong Answer

Solution code:
(n,m),*l=[list(map(int,s.split()))for s in open(0)];d=[0]*2+[9e99]*n
for i in range(n*2):
 for a,b,c in l:
  if d[b]>d[a]-c:d[b]=[d[a]-c,-9e99][i>n]
 if i==n:x=d[n]
print([max(-x,0),-1][d[n]!=x])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(m)]
data=[[] for i in range(n+1)]
for u in abc:
    a,b,c=u
    data[a].append([b,c])
inf=float("inf")
lst=[-inf]*(n+1)
lst[1]=0
que=[1]
count=0
flag=[0]*(n+1)
while que:
    h=[]
    for u in que:
        for v in data[u]:
            w,c=v
            if lst[u]+c>lst[w]:
                lst[w]=lst[u]+c
                h.append(w)
    que=h
    count+=1
    if count==m+2:
        print("inf")
        break
else:
    print(lst[n])

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(m)]
data=[[] for i in range(n+1)]
for u in abc:
    a,b,c=u
    data[a].append([b,c])
inf=float("inf")
lst=[-inf]*(n+1)
lst[1]=0
que=[1]
count=0
while que:
    h=[]
    for u in que:
        for v in data[u]:
            w,c=v
            if lst[u]+c>lst[w]:
                lst[w]=lst[u]+c
                h.append(w)
    que=h
    count+=1
    if count==m+1:
        print("inf")
        break
else:
    print(lst[n])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
N,M=map(int, sys.stdin.readline().split())
edge=[ map(int, sys.stdin.readline().split()) for _ in range(M) ]   #辺

dp=[ float("-inf") for _ in range(N+1) ]
dp[1]=0

for i in range(N):
    for fro,to,cost in edge:
        alt=dp[fro]+cost
        if dp[to]<alt:
            dp[to]=alt
            if i==N-1:
                print float("inf")
                quit()
print dp[N]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
N,M=map(int, sys.stdin.readline().split())
edge=[ map(int, sys.stdin.readline().split()) for _ in range(M) ]   #辺

dp=[ float("-inf") for _ in range(N+1) ]
dp[1]=0

for i in range(N):
    for fro,to,cost in edge:
        alt=dp[fro]+cost
        if dp[to]<alt:
            dp[to]=alt

print dp[N]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
N,M=map(int, sys.stdin.readline().split())
edge=[ map(int, sys.stdin.readline().split()) for _ in range(M) ]   #辺

dp=[ float("-inf") for _ in range(N+1) ]
dp[1]=0

for i in range(N+1):
    for fro,to,cost in edge:
        alt=dp[fro]+cost
        if dp[to]<alt:
            if i==N:
                print float("inf")
                quit()
            dp[to]=alt

print dp[N]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
N,M=map(int, sys.stdin.readline().split())
edge=[ map(int, sys.stdin.readline().split()) for _ in range(M) ]   #辺

dp=[ float("-inf") for _ in range(N+1) ]
dp[1]=0

for i in range(N):
    for fro,to,cost in edge:
        alt=dp[fro]+cost
        if dp[to]<alt:
            if i==N-1:
                print float("inf")
                quit()
            dp[to]=alt

print dp[N]

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M=map(int,input().split())
out=[set() for i in range(N+1)];out[0]=None # 1-initial
w=[[None for j in range(N+1)] for i in range(N+1)]
for k in range(M):
    a,b,c=map(int,input().split())
    out[a].add(b)
    w[a][b]=c
p=[None for i in range(N+1)];p[1]=0

q=deque()
q.append(1)
cnt=0
f=False # 重み正のループあり
while q:
    u=q.popleft()
    for v in out[u]:
        if p[v] is None or p[u]+w[u][v]>p[v]:
            p[v]=p[u]+w[u][v]
            q.append(v)
            cnt+=1
    if cnt>N:
        f=True
        break
print('inf' if f else p[N])

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M=map(int,input().split())
out=[set() for i in range(N+1)];out[0]=None # 1-initial
w=[[None for j in range(N+1)] for i in range(N+1)]
for k in range(M):
    a,b,c=map(int,input().split())
    out[a].add(b)
    w[a][b]=c
p=[None for i in range(N+1)];p[1]=0

q=deque()
q.append(1)
cnt=0
f=False # 重み正のループあり
while q:
    u=q.popleft()
    for v in out[u]:
        if p[v] is None or p[u]+w[u][v]>p[v]:
            p[v]=p[u]+w[u][v]
            q.append(v)
            cnt+=1
    if cnt>M:
        f=True
        break
print('inf' if f else p[N])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(m)]
d = [-float('inf')]*(n+1)
d[1] = 0
for _ in range(n):
    for i,j,c in e:
        d[j] = max(d[j], d[i]+c)
if any(d[j]<d[i]+c for i,j,c in e):
    print('inf')
else:
    print(d[n])

Submission status: Wrong Answer

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()

from scipy.sparse import csr_matrix #pypyだとエラーになるので、pythonを使うこと
from scipy.sparse.csgraph import dijkstra, floyd_warshall, bellman_ford

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

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

graph = csr_matrix((c, (a, b)), shape=(N, N))
try:
	dist1 = bellman_ford(graph, directed=True, indices=[0])
except:
	print("inf")
	exit()
list(dist1)
print(int(-dist1[0][-1]))

Submission status: Wrong Answer

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()

from scipy.sparse import csr_matrix #pypyだとエラーになるので、pythonを使うこと
from scipy.sparse.csgraph import dijkstra, floyd_warshall, bellman_ford

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

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

graph = csr_matrix((c, (a, b)), shape=(N, N))
try:
	dist1 = bellman_ford(graph, directed=True, indices=0)
except:
	print("inf")
	exit()
list(dist1)
print(int(-dist1[-1]))

Submission status: Wrong Answer

Solution code:
from collections import deque
INFTY = 10**14
def dist(s):
    cmax = -INFTY
    d = [-INFTY for _ in range(N+1)]
    d[1]=0
    cnt = 0
    heap = deque([1])
    while heap:
        cur = heap.popleft()
        if cur in G:
            for x in G[cur]:
                if d[x[0]]<d[cur]+x[1]:
                    d[x[0]] = d[cur]+x[1]
                    heap.append(x[0])
                    cnt += 1
        if cnt>N*M:break
    return d[N],cnt
        
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b,c = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append((b,c))
d,cnt = dist(1)
if cnt<=N*M:
    print(d)
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
from collections import deque
INFTY = 10**14
def dist(s):
    cmax = -INFTY
    d = [-INFTY for _ in range(N+1)]
    d[1]=0
    cnt = 0
    heap = deque([1])
    while heap:
        cur = heap.popleft()
        if cur in G:
            for x in G[cur]:
                if d[x[0]]<d[cur]+x[1]:
                    d[x[0]] = d[cur]+x[1]
                    heap.append(x[0])
                    cnt += 1
        if cnt>M:break
    return d[N],cnt
        
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b,c = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append((b,c))
d,cnt = dist(1)
if cnt<=M:
    print(d)
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
from collections import deque
INFTY = 10**13
def dist(s):
    cmax = -INFTY
    d = [-INFTY for _ in range(N+1)]
    d[1]=0
    cnt = 0
    heap = deque([1])
    while heap:
        cur = heap.popleft()
        if cur in G:
            for x in G[cur]:
                if d[x[0]]<d[cur]+x[1]:
                    d[x[0]] = d[cur]+x[1]
                    heap.append(x[0])
                    cnt += 1
        if cnt>M:break
    return d[N],cnt
        
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b,c = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append((b,c))
d,cnt = dist(1)
if cnt<=M:
    print(d)
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
from collections import deque
INFTY = 10**13
def dist(s):
    cmax = -INFTY
    d = [-INFTY for _ in range(N+1)]
    d[1]=0
    cnt = 0
    heap = deque([1])
    while heap:
        cur = heap.popleft()
        if cur in G:
            for x in G[cur]:
                if d[x[0]]<d[cur]+x[1]:
                    d[x[0]] = d[cur]+x[1]
                    heap.append(x[0])
                    cnt += 1
        if cnt>N*N:break
    return d[N],cnt
        
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b,c = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append((b,c))
d,cnt = dist(1)
if cnt<=N*N:
    print(d)
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
from collections import deque
INFTY = 10**13
def dist(s):
    cmax = -INFTY
    d = [-INFTY for _ in range(N+1)]
    d[1]=0
    cnt = 0
    heap = deque([1])
    while heap:
        cur = heap.popleft()
        if cur in G:
            for x in G[cur]:
                if d[x[0]]<d[cur]+x[1]:
                    d[x[0]] = d[cur]+x[1]
                    heap.append(x[0])
                    cnt += 1
        if cnt>N:break
    return d[N],cnt
        
N,M = map(int,input().split())
G = {}
for _ in range(M):
    a,b,c = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append((b,c))
d,cnt = dist(1)
if cnt<=N:
    print(d)
else:
    print("inf")

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

n, m = map(int, input().split())
ro ,co, w = [], [], []
for i in range(m):
    a, b, c = map(int, input().split())
    ro.append(a-1)
    co.append(b-1)
    w.append(-c)
g = csr_matrix((w, (ro, co)), shape=(n, n))
try:
    bell = bellman_ford(g, indices=0)
    print(int(-bell[-1]))
except:
    print('inf')

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

n,m=map(int,input().split())
ro,co,w=[],[],[]
for i in range(m):
    a,b,c=map(int,input().split())
    ro.append(a-1)
    co.append(b-1)
    w.append(-c)
g=csr_matrix((w,(ro,co)),shape=(n,n))
try:
    bell=bellman_ford(g,indices=0)
    print(int(-bell[-1]))
except:
    print('inf')