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:
def BellmanFord(sv, ev, cv, 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 s,e,c in zip(sv, ev, cv):
      if dist[0] != inf and dist[e-1] > dist[s-1] + c:
        dist[e-1] = dist[s-1] + c
        if i==num_v-1: return "inf"
  
  return dist[-1]*-1

N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
  aa, bb, cc = map(int, input().split())
  a.append(aa)
  b.append(bb)
  c.append(cc*-1)

print(BellmanFord(a, b, c, N, 1))

Submission status: Wrong Answer

Solution code:
def BellmanFord(sv, ev, cv, 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 s,e,c in zip(sv, ev, cv):
      if dist[0] != inf and dist[e-1] > dist[s-1] + c:
        dist[e-1] = dist[s-1] + c
        if i==num_v-1: return ["inf"]
  
  return dist[-1]*-1

N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
  aa, bb, cc = map(int, input().split())
  a.append(aa)
  b.append(bb)
  c.append(cc*-1)

print(BellmanFord(a, b, c, N, 1))

Submission status: Wrong Answer

Solution code:
def BellmanFord(sv, ev, cv, 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 s,e,c in zip(sv, ev, cv):
      if dist[0] != inf and dist[e-1] > dist[s-1] + c:
        dist[e-1] = dist[s-1] + c
        if i==num_v-1: return ["inf"]
  
  return dist

N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
  aa, bb, cc = map(int, input().split())
  a.append(aa)
  b.append(bb)
  c.append(cc*-1)

print(BellmanFord(a, b, c, N, 1)[-1])

Submission status: Wrong Answer

Solution code:
def BellmanFord(sv, ev, cv, 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 s,e,c in zip(sv, ev, cv):
      if dist[0] != inf and dist[e-1] > dist[s-1] + c:
        dist[e-1] = dist[s-1] + c
        if i==num_v-1: return "inf"
  
  return dist[num_v-1]*-1

N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
  aa, bb, cc = map(int, input().split())
  a.append(aa-1)
  b.append(bb-1)
  c.append(cc*-1)

print(BellmanFord(a, b, c, N, 1))

Submission status: Wrong Answer

Solution code:
def BellmanFord(sv, ev, cv, 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 s,e,c in zip(sv, ev, cv):
      if dist[0] != inf and dist[e-1] > dist[s-1] + c:
        dist[e-1] = dist[s-1] + c
        if i==num_v-1: return "inf"
  
  return dist[num_v-1]*-1

N, M = map(int, input().split())
a, b, c = [], [], []
for i in range(M):
  aa, bb, cc = map(int, input().split())
  a.append(aa)
  b.append(bb)
  c.append(cc*-1)

print(BellmanFord(a, b, c, N, 1))

Submission status: Wrong Answer

Solution code:
def solve(n, m, ABC):
    distance = [None] * n
    distance[0] = 0

    for _ in range(n - 1):
        for a, b, c in ABC:
            if distance[a - 1] is None:
                continue
            if distance[b - 1] is None or distance[b - 1] < distance[a - 1] + c:
                distance[b - 1] = distance[a - 1] + c

    inf = False
    for a, b, c in ABC:
        if distance[a - 1] is None or distance[b - 1] is None:
            continue
        if b == n and distance[b - 1] < distance[a - 1] + c:
            inf = True

    return 'inf' if inf else distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Wrong Answer

Solution code:
def solve(n, m, ABC):
    distance = [None] * n
    distance[0] = 0

    for _ in range(n - 1):
        for a, b, c in ABC:
            if distance[a - 1] is None:
                continue
            if distance[b - 1] is None or distance[b - 1] < distance[a - 1] + c:
                distance[b - 1] = distance[a - 1] + c

    for a, b, c in ABC:
        if distance[a - 1] is None or distance[b - 1] is None:
            continue
        if distance[b - 1] < distance[a - 1] + c:
            return 'inf'

    return distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Wrong Answer

Solution code:
def solve(n, m, ABC):
    distance = [None] * n
    distance[0] = 0

    for _ in range(n - 1):
        for a, b, c in ABC:
            if distance[a - 1] is None:
                continue
            if distance[b - 1] is None or distance[b - 1] < distance[a - 1] + c:
                distance[b - 1] = distance[a - 1] + c

    for a, b, c in ABC:
        if distance[a - 1] is None:
            continue
        if distance[b - 1] is None or distance[b - 1] < distance[a - 1] + c:
            return 'inf'

    return distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(300000)

def solve(n, m, ABC):
    g = [[] for _ in range(n)]
    for a, b, c in ABC:
        g[a - 1].append((b - 1, c))

    distance = [-10 ** 10] * n
    distance[0] = 0
    parents = [-1] * n
    ng = [False]

    def search(node):
        if ng[0]:
            return
        for to, d in g[node]:
            if node == parents[to] and distance[to] < distance[node] + d:
                ng[0] = True
                return
            if distance[to] < distance[node] + d:
                distance[to] = distance[node] + d
                parents[to] = node
            search(to)

    search(0)
    return 'inf' if ng[0] else distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Wrong Answer

Solution code:
def solve(n, m, ABC):
    distance = [-10 ** 10] * n
    distance[0] = 0

    for _ in range(n):
        for a, b, c in ABC:
            if distance[b - 1] < distance[a - 1] + c:
                distance[b - 1] = distance[a - 1] + c

    for a, b, c in ABC:
        if distance[b - 1] < distance[a - 1] + c:
            return 'inf'

    return distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Wrong Answer

Solution code:
def solve(n, m, ABC):
    distance = [-10 ** 10] * n
    distance[0] = 0

    for _ in range(n - 1):
        for a, b, c in ABC:
            if distance[b - 1] < distance[a - 1] + c:
                distance[b - 1] = distance[a - 1] + c

    for a, b, c in ABC:
        if distance[b - 1] < distance[a - 1] + c:
            return 'inf'

    return distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Submission status: Wrong Answer

Solution code:
def solve():
    N,M = map(int, input().split())
    graph_cod = [[] for _ in range(N+1)]
    min_val = -1*(10**18)
    for _ in range(M):
        a,b,c = map(int, input().split())
        graph_cod[b].append((a,c))
        
    ret = 0
    stack = [N]
    searched = [False]*(N+1)
    searched[N] = True
    
    distance = [min_val]*(N+1)
    distance[N] = 0
    while stack or graph_cod[N]:
        if not stack:
            searched = [False]*(N+1)
            searched[N] = True
            stack.append(N)
        
        cod = stack.pop()
        if not graph_cod[cod]: continue
            
        dom,w = graph_cod[cod].pop()
        if searched[dom]:
            print('inf')
            return
        
        searched[dom] = True
        distance[dom] = max(distance[dom], distance[cod]+w)
        # print(cod,dom, w, distance)
        stack.append(dom)
        
    print(distance[dom])
    
solve()

Submission status: Wrong Answer

Solution code:
def solve():
    N,M = map(int, input().split())
    graph_cod = [[] for _ in range(N+1)]
    min_val = -1*(10**18)
    for _ in range(M):
        a,b,c = map(int, input().split())
        graph_cod[b].append((a,c))
        
    ret = 0
    stack = [N]
    searched = [False]*(N+1)
    searched[N] = True
    
    distance = [min_val]*(N+1)
    distance[N] = 0
    while stack or graph_cod[N]:
        if not stack:
            searched = [False]*(N+1)
            searched[N] = True
            stack.append(N)
        
        cod = stack.pop()
        if not graph_cod[cod]: continue
            
        dom,w = graph_cod[cod].pop()
        if searched[dom]:
            print('inf')
            return
        distance[dom] = max(distance[dom], distance[cod]+w)
        # print(cod,dom, w, distance)
        stack.append(dom)
        
    print(distance[dom])
    
solve()

Submission status: Wrong Answer

Solution code:
def bellmanford(num, start, goal, edges):
    cost = [float('inf')] * num
    cost[start] = 0
    for _ in range(num):
        updated = False
        for a, b, c in edges:
            if cost[b] > cost[a] + c:
                cost[b] = cost[a] + c
                updated = True
        if not updated:
            break
        else:
            return (-1,cost)
    return (1,-cost[goal])

def main():
    N, M = LI()
    v = []
    for _ in range(M):
        x, y, z = map(int, input().split())
        v.append((x - 1, y - 1, -z))
#    print(v)
#    print(bellmanford(N, 0, N-1, v))
    cur, d = bellmanford(N, 0, N - 1, v)
    if cur == -1:
        inf_flag = [False] * N
        for _ in range(N):
            for f, t, c in v:
                if d[f] == inf: continue
                if inf_flag[f] == True:
                    inf_flag[t] = True
                if d[t] > d[f] + c:
                    d[t] = d[f] + c
                    inf_flag[t] = True
        print("inf" if inf_flag[N - 1] else -d[N - 1])
    else:
        print(d)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    main()

"""
3 3
1 2 4
2 3 3
1 3 5
"""

Submission status: Wrong Answer

Solution code:

def Bellman_Ford(node_num:int,start:int,VWC:list)->list:
    Ans = [float("inf")]*(node_num + 1)
    node = start
    Ans[start] = 0
    changeable = {start:True}
    edge = [[ ] for _ in range(node_num + 1)]
    for v,w,c in VWC:
        edge[v].append(w)
    stack = [start]
    while len(stack) > 0:
        node = stack.pop(-1)
        for e in edge[node]:
            if e not in changeable:
                stack.append(e)
                changeable[e] = True
        
    for _ in range(node_num-1):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    Pre = list(Ans)
    for _ in range(node_num):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    for node in changeable.keys():
        if Ans[node] == Pre[node]:
            return Ans
    return [float("inf")]*(node_num + 1)

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in  range(M)]
    newABC = [[a,b,-c] for a,b,c in ABC]
    Ans1 = Bellman_Ford(N,1,newABC)
    print("inf" if Ans1[N] == float("inf") else -Ans1[N])
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

def Bellman_Ford(node_num:int,start:int,VWC:list)->list:
    Ans = [float("inf")]*(node_num + 1)
    node = start
    Ans[start] = 0
    changeable = {}
    edge = [[ ] for _ in range(node_num + 1)]
    for v,w,c in VWC:
        edge[v].append(w)
    stack = [start]
    while len(stack) > 0:
        node = stack.pop(-1)
        for e in edge[node]:
            if e not in changeable:
                stack.append(e)
                changeable[e] = True
        
    for _ in range(node_num-1):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    Pre = list(Ans)
    for _ in range(node_num):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    for node in changeable.keys():
        if Ans[node] == Pre[node]:
            return Ans
    return [float("inf")]*(node_num + 1)

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in  range(M)]
    newABC = [[a,b,-c] for a,b,c in ABC]
    Ans1 = Bellman_Ford(N,1,newABC)
    print("inf" if Ans1[N] == float("inf") else -Ans1[N])
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

def Bellman_Ford(node_num:int,start:int,VWC:list)->list:
    Ans = [float("inf")]*(node_num + 1)
    node = start
    Ans[start] = 0
    changeable = {}
    for v,w,c in VWC:
        if v not in changeable:
            changeable[v] = True
        if w not in changeable:
            changeable[w] = True
        
    for _ in range(node_num-1):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    Pre = list(Ans)
    for _ in range(3*(node_num-1)):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    for node in changeable.keys():
        if Ans[node] == Pre[node]:
            return Ans
    return [float("inf")]*(node_num + 1)

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in  range(M)]
    newABC = [[a,b,-c] for a,b,c in ABC]
    Ans1 = Bellman_Ford(N,1,newABC)
    print("inf" if Ans1[N] == float("inf") else -Ans1[N])
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

def Bellman_Ford(node_num:int,start:int,VWC:list)->list:
    Ans = [float("inf")]*(node_num + 1)
    node = start
    Ans[start] = 0
    changeable = {}
    for v,w,c in VWC:
        if v not in changeable:
            changeable[v] = True
        if w not in changeable:
            changeable[w] = True
        
    for _ in range(node_num-1):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    Pre = list(Ans)
    for _ in range(2*(node_num-1)):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    for node in changeable.keys():
        if Ans[node] == Pre[node]:
            return Ans
    return [float("inf")]*(node_num + 1)

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in  range(M)]
    newABC = [[a,b,-c] for a,b,c in ABC]
    Ans1 = Bellman_Ford(N,1,newABC)
    print("inf" if Ans1[N] == float("inf") else -Ans1[N])
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
sec = []
for i in range(M):
    a,b,t = list(map(int,input().split()))
    a -= 1
    b -= 1
    sec.append((a,b,t))
from heapq import heappush, heappop
INF = float('inf')
def ford(start,node,sec):
    dist = [-INF] * node
    dist[start] = 0
    while True:
        update = True
        flag = False
        for i in range(len(sec)):
            st,en,cost = sec[i]
            if dist[st] != -float('inf') and dist[en] < dist[st]+cost:
                dist[en] = dist[st]+cost
                update=False
                if i == node-1:
                    flag = True
                    break
        if flag:
            return [0,float('inf')]
        if update:
            break
    return dist
gmax = ford(0,N,sec)
print(gmax[-1]-gmax[0])

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
sec = []
for i in range(M):
    a,b,t = list(map(int,input().split()))
    a -= 1
    b -= 1
    sec.append((a,b,t))
from heapq import heappush, heappop
INF = float('inf')
def ford(start,node,sec):
    dist = [-INF] * node
    dist[start] = 0
    while True:
        update = True
        flag = False
        for i in range(len(sec)):
            st,en,cost = sec[i]
            if dist[st] != -float('inf') and dist[en] < dist[st]+cost:
                dist[en] = dist[st]+cost
                update=False
                if i == node-1:
                    flag = True
                    break
        if flag:
            return [float('inf')]
        if update:
            break
    return dist
gmax = ford(0,N,sec)
print(gmax[-1]-gmax[0])

Submission status: Wrong Answer

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

INF = 10**20
V = [INF]*N
V[0] = 0
for _ in range(N):
  for a, b, c in E:
    d = V[a]+c
    if d < V[b]: V[b] = d

for a, b, c in E:
  if V[a]+c<V[b]:
    print('inf')
    exit()
    
print(-V[-1])

Submission status: Wrong Answer

Solution code:
#ABC061D - Score Attack
#https://atcoder.jp/contests/abc061/tasks/abc061_d
#自己考察

import sys
n, m = list(map(int,input().split()))
lst = [[] for _ in range(n+1)]#*(n+1)の挙動がよくわからない
for i in range(m):
    a, b, c = list(map(int,input().split()))
    lst[a].append((b,-c))
dp = [float("Inf")]*(n+1)
dp[1] = 0

for _ in range(n):
    for f in range(1,n+1):
        if dp[f] != float("Inf"):
            for t, c in lst[f]:
                dp[t] = min(dp[t], dp[f] + c)

for f in range(1,n+1):
    for t,c in lst[f]:
        if dp[t] > dp[f] + c:
            dp[n] = -float("Inf")

print(-dp[n])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

# Bellman-Ford法
# ベルマンフォード法

N, M = map(int, input().split())
#EDGES = [[] for _ in range(N+1)]
EDGES = []

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

INF = 10 ** 18
d = [INF] * (N+1)
d[1] = 0

for k in range(N):
    update = False
    for i in range(M):
        a, b, c = EDGES[i]
        if d[a] != INF and d[b] > d[a] + c:
            d[b] = d[a] + c
            update = True

    if not update:
        break

    if k == N-2 and update:
        print('inf')
        exit()

print(-d[N])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

# Bellman-Ford法
# ベルマンフォード法

N, M = map(int, input().split())
#EDGES = [[] for _ in range(N+1)]
EDGES = []

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

INF = 10 ** 18
d = [INF] * (N+1)
d[1] = 0

for v in range(N):
    update = False
    for i in range(M):
        a, b, c = EDGES[i]
        if d[a] != INF and d[b] > d[a] + c:
            d[b] = d[a] + c
            update = True

    if not update:
        break

    if v == N-1 and update:
        print('inf')
        exit()

print(-d[N])

Submission status: Wrong Answer

Solution code:
import sys
sys.stdin.readline

def main():
    N, M = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(M)]
    INF = float("inf")
    cost = [-INF] * N
    cost[0] = 0
    for i in range(N):
        for a, b, c in ABC:
            if cost[b-1] < cost[a-1] + c:
                cost[b-1] = cost[a-1] + c
                if i == N - 1:
                    print("inf")
                    exit()
    print(cost[N-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def shortest_path(s,n,w,es):
#s→iの最短距離
# s:始点, n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float('inf')] * n
    #d[i] : s→iの最短距離
    d[s] = 0
    while True:
        update=False
        for p,q,r in es:
        # e: 辺iについて [from,to,cost]
            #print(d,p,q,r)
            if d[p] != float('inf') and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
            ans1=d[-1]
        return -ans1
        
def find_negative_loop(n,w,es):
    #負の経路の検出
    #n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float("inf")] * n
    d[0] = 0 
    #この始点はどこでもよい
    for i in range(n):
        for j in range(w):
            e = es[j]
            if d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                if i == n-1:
                    return True
    return False
################
n,w = map(int,input().split()) #n:頂点数　w:辺の数
es = [] #es[i]: [辺の始点,辺の終点,辺のコスト]
for _ in range(w):
 x,y,z = map(int,input().split())
 es.append([x-1,y-1,-z])
if find_negative_loop(n,w,es)==True:
    print('inf')
else:
    print(shortest_path(0,n,w,es))

Submission status: Wrong Answer

Solution code:
def shortest_path(s,n,w,es):
#s→iの最短距離
# s:始点, n:頂点数, w:辺の数, es[i]: [辺の始点,辺の終点,辺のコスト]
    d = [float('-inf')] * n
    #d[i] : s→iの最短距離
    d[s] = 0
    while True:
        update = False
        for p,q,r in es:
            p-=1
            q-=1
        # e: 辺iについて [from,to,cost]
            #print(d,p,q,r)
            if d[p] != float('-inf') and d[q] < d[p] + r:
                d[q] = d[p] + r
                update = True
            if not update:
                break
        return d[-1]
################
n,w = map(int,input().split()) #n:頂点数　w:辺の数
es = [] #es[i]: [辺の始点,辺の終点,辺のコスト]
for _ in range(w):
 x,y,z = map(int,input().split())
 es.append([x,y,z])
print(shortest_path(0,n,w,es))

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
N,M=map(int,input().split())
a,b,c=[],[],[]
for _ in range(M):
  ai,bi,ci=map(int,input().split())
  a.append(ai-1)
  b.append(bi-1)
  c.append(-ci)
cost=csr_matrix((c, (a, b)), shape=(N, N), dtype=int)
try:
  x=bellman_ford(cost, indices=[0])
  print(-int(x[0][N-1]))
except scipy.sparse.csgraph._shortest_path.NegativeCycleError:
  print('inf')

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
N,M=map(int,input().split())
a,b,c=[],[],[]
for _ in range(M):
  ai,bi,ci=map(int,input().split())
  a.append(ai-1)
  b.append(bi-1)
  c.append(-ci)
cost=csr_matrix((c, (a, b)), shape=(N, N), dtype=int)
try:
  print(int(-bellman_ford(cost)[0][N-1]))
except scipy.sparse.csgraph._shortest_path.NegativeCycleError:
  print('inf')

Submission status: Wrong Answer

Solution code:
N,M=[int(x) for x in input().split()]
adj=[[] for i in range(N)]



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


visited=[0 for i in range(N)]

visited[0]=1

import heapq
queue=adj[0]
heapq.heapify(queue)

ans=0
counter=1

while queue:
	temp=heapq.heappop(queue)
	vertex,cost=temp
	if visited[vertex]==1:
		break
		counter=0
	elif vertex==N-1:
		ans+=cost
		visited[vertex]=1
		for v,c in adj[vertex]:
			if visited[v]==1:
				counter=0
				break
	else:
		ans+=cost
		visited[vertex]=1
		for trash in adj[vertex]:
			heapq.heappush(queue,trash)

if counter==0:
	print("inf")
else:
	print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

def mii():
    return map(int, input().split())


def resolve():
    N, M = mii()
    ab = [[] for i in range(N)]
    for i in range(M):
        a, b, c = mii()
        ab[a-1].append((b-1, c))

    INF = 10**9*N + 1
    dp = [INF] * N
    dp[0] = 0
    for i in range(N):
        for p1 in range(N):
            if dp[p1] == INF: continue

            for p2, t2 in ab[p1]:
                t3 = dp[p1] - t2
                if t3 < dp[p2]:
                    dp[p2] = t3

                    if i == N-1:
                        print("inf")
                        return

    print(-dp[-1])

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
#!python3

def mii():
    return map(int, input().split())

from heapq import heappush, heappop

def resolve():
    N, M = mii()
    ab = [[] for i in range(N)]
    for i in range(M):
        a, b, c = mii()
        ab[a-1].append((b-1, c))

    used = [False] * N
    q = [(0, set())]
    while q:
        p1, s1 = q.pop()

        for p2, x in ab[p1]:
            if p2 in s1:
                print("inf")
                return

            s2 = set(s1)
            s2.add(p2)
            q.append((p2, s2))

    q = []
    heappush(q, (0, 0))
    dp = [10**9*N+1] * N
    while q:
        t1, p1 = heappop(q)

        for p2, t2 in ab[p1]:
            t3 = t1 - t2
            if t3 < dp[p2]:
                dp[p2] = t3
                heappush(q, (t3, p2))

    print(-dp[-1])


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 14
    n, m = MI()
    ee = []
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ee.append([a, b, -c])

    score = [inf] * n
    score[0] = 0
    for _ in range(n):
        change = False
        for a, b, c in ee:
            if score[a]+c<score[b]:
                score[b]=score[a]+c
                change=True
        if not change:
            print(-score[n-1])
            break
    else:
        print("inf")

main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 14
    n, m = MI()
    ee = []
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ee.append([a, b, -c])

    score = [inf] * n
    score[0] = 0
    for _ in range(m):
        change = False
        for a, b, c in ee:
            if score[a]+c<score[b]:
                score[b]=score[a]+c
                change=True
        if not change:
            print(-score[n-1])
            break
    else:
        print("inf")

main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u,s=0):
        route[u]=True
        for v,c in ot[u]:
            if route[v]:
                if s+c>score[v]:
                    return True
                continue
            if dfs(v,s+c):return True
            score[u]=max(score[u],score[v]+c)
        route[u]=False
        return False

    inf = 10 ** 14
    n, m = MI()
    ot = defaultdict(list)
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ot[b].append([a, c])

    score = [-inf] * n
    score[0]=0
    route=[False]*n
    if dfs(n-1):
        print("inf")
    else:
        print(score[n-1])

main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u,s=0):
        route[u]=True
        for v,c in ot[u]:
            if score[v]!=-1 and route[v]:
                if s+c>score[v]:
                    return True
                return False
            if dfs(v,s+c):return True
            score[u]=max(score[u],score[v]+c)
        route[u]=False
        return False

    inf = 10 ** 14
    n, m = MI()
    to = defaultdict(list)
    ot = defaultdict(list)
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        to[a].append([b, c])
        ot[b].append([a, c])

    score = [-inf] * n
    score[0]=0
    route=[False]*n
    if dfs(n-1):
        print("inf")
    else:
        print(score[n-1])

main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u, s=0):
        if route[u]:
            if s>score[u]:
                return True
            return False
        route[u]=True
        score[u]=max(score[u],s)
        for v,c in to[u]:
            if dfs(v,s+c):return True
        route[u]=False
        return False

    inf = 10 ** 14
    n, m = MI()
    to = defaultdict(list)
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        to[a].append([b, c])

    score = [-inf] * n
    route=[False]*n
    if dfs(0):
        print("inf")
    else:
        print(score[n-1])

main()