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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

cost = [-float("INF")]*(N+1)
cost[1] = 0
cnt = 0
flag = True
while flag:
    flag = False
    cnt += 1
    if cnt > N+1:
        print("inf")
        exit()
    for a,b,c in edges:
        if cost[a]+c > cost[b]:
            flag = True
            cost[b] = cost[a]+c
print(cost[N])

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

n, m = map(int, input().split()) # n:頂点数, m:辺の数
g = []
for _ in range(m):
    x, y, z = map(int, input().split()) # 始点,終点,コスト
    x -= 1
    y -= 1
    z *= -1
    g.append([x, y, z])

ans = bellman_ford(0)
#print(ans)
print(-ans[n-1] if ans else "inf")

Submission status: Wrong Answer

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

n, m = map(int, input().split()) # n:頂点数, m:辺の数
g = []
for _ in range(m):
    x, y, z = map(int, input().split()) # 始点,終点,コスト
    x -= 1
    y -= 1
    z *= -1
    g.append([x, y, z])

ans = bellman_ford(0)
#print(ans)
print(-ans[n-1] if ans else "inf")

Submission status: Wrong Answer

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

n, m = map(int, input().split()) # n:頂点数, m:辺の数
g = []
for _ in range(m):
    x, y, z = map(int, input().split()) # 始点,終点,コスト
    x -= 1
    y -= 1
    z *= -1
    g.append([x, y, z])

ans = bellman_ford(0)
print(-ans[n-1] if ans else "inf")

Submission status: Wrong Answer

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

n, m = map(int, input().split()) # n:頂点数, w:辺の数
g = []
for _ in range(m):
    x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
    x -= 1
    y -= 1
    z *= -1
    g.append([x, y, z])

ans = -bellman_ford(0, n-1)
print(ans if ans < INF else "inf")

Submission status: Wrong Answer

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

n, m = map(int, input().split()) # n:頂点数, w:辺の数
g = []
for _ in range(m):
    x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
    x -= 1
    y -= 1
    z *= -1
    g.append([x, y, z])

ans = -bellman_ford(0, n-1)
print(ans if ans > -INF else "inf")

Submission status: Wrong Answer

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

n, m = map(int, input().split()) # n:頂点数, w:辺の数
g = []
for _ in range(m):
    x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
    x -= 1
    y -= 1
    z *= -1
    g.append([x, y, z])

ans = -bellman_ford(0)
print(ans if ans > -INF else "inf")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
INF=float('inf')
G=[]
for _ in range(m):
  a,b,c=map(int,input().split())
  G.append([a-1,b-1,-c])
  
def main():
  D=[INF for _ in range(n)]
  D[0]=0
  for i in range(n):
    for x,y,z in G:
      if D[x]!=INF and D[y]>D[x]+z:
        D[y]=D[x]+z
        if i==n-1:
          return 'inf'
  return -D[n-1]
   
if __name__=='__main__':
  print(main())

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
INF=float('inf')
G=[]
for _ in range(m):
  a,b,c=map(int,input().split())
  G.append([a-1,b-1,-c])
  
def main():
  D=[INF for _ in range(n)]
  D[0]=0
  for i in range(n):
    update=False
    for x,y,z in G:
      if D[x]!=INF and D[y]>D[x]+z:
        D[y]=D[x]+z
        update=True
    if not update:
      break
    if i==n-1:
      return 'inf'
  return -D[n-1]
   
if __name__=='__main__':
  print(main())

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
INF=float('inf')
G=[]
for _ in range(m):
  a,b,c=map(int,input().split())
  G.append([a-1,b-1,-c])
  
def main():
  D=[INF for _ in range(n)]
  D[0]=0
  for i in range(n):
    update=False
    for x,y,z in G:
      if D[y]>D[x]+z:
        D[y]=D[x]+z
        update=True
    if not update:
      break
    if i==n-1:
      return 'inf'
  return -D[n-1]
   
if __name__=='__main__':
  print(main())

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
INF=float('inf')
G=[]
cycle=0
for _ in range(m):
  a,b,c=map(int,input().split())
  G.append([a,b,-c])
D=[INF for i in range(n+1)]
D[1]=0
for i in range(1,n+1):
  update=False
  for x,y,z in G:
    if D[y]>D[x]+z:
      D[y]=D[x]+z
      update=True
  if not update:
    break
  if i==n:
    cycle=1
if cycle==1:
  print('inf')
else:
  print(-D[n])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
N,M = map(int,input().split())
abc = [list(map(int,input().split())) for i in range(M)]

g = defaultdict(list)
for a,b,c in abc:
    g[a].append((b,c))

inf = 10**20
score = [-inf]*(N+1)
score[1] = 0

for i in range(N+1):
    update = False
    for v in range(1,N+1):
        for nv, c in g[v]:
            if score[v] + c > score[nv]:
                score[nv] = score[v] + c
                update = True
    if not update:
        break
else:
    print('inf')
    exit()

print(score[N])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
N,M = map(int,input().split())
abc = [list(map(int,input().split())) for i in range(M)]

g = defaultdict(list)
for a,b,c in abc:
    g[a].append((b,c))

inf = 10**15
score = [-inf]*(N+1)
score[1] = 0

for i in range(N+1):
    update = False
    for v in range(1,N+1):
        for nv, c in g[v]:
            if score[v] + c > score[nv]:
                score[nv] = score[v] + c
                update = True
    if not update:
        break
else:
    print('inf')
    exit()

print(score[N])

Submission status: Wrong Answer

Solution code:
def bellman_ford(vertexes, edges, costs, start):
    # cost to each vertex
    d = [-float("inf")] * vertexes
    # start cost is zero
    d[start] = 0
    for i in range(vertexes):
        update = False
        for j in range(len(edges)):
            frm, to = edges[j]
            cost = costs[j]
            if d[to] < d[frm] + cost:
                d[to] = d[frm] + cost
                update = True
        # stop if not updated
        if not update:
            break

        # find if closed-loop exists
        if i == n - 1:
            return -1

    return d


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

edges = []
costs = [-float("inf")] * (m)
score = [-float("inf")] * (n + 1)

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

d = bellman_ford(n, edges, costs, 0)

if d == -1:
    print("inf")
else:
    print(d[n - 1])

Submission status: Wrong Answer

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

def main():
    N, M = map(int, input().split())
    edges = []  # ベルマンフォードするなら頂点よりも辺が主役なので
    for _ in range(M):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        edges.append((a, b, c))
    """
    辺の重みを正負逆転させることで単一始点最短経路問題を解けば良い。
    ベルマンフォードで負閉路を検出したら"inf"を返す。
    ABC137Eを参考にする。
    """
    d = [float("inf")] * N
    d[0] = 0
    step = 0
    update = True
    while update:
        update = False
        for a, b, c in edges:
            new_cost = d[a] - c
            if new_cost < d[b]:
                update = True
                d[b] = new_cost
        step += 1
        if step > N:
            print("inf")
            return
    print(-d[N - 1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    N, M = map(int, input().split())
    edges = []  # ベルマンフォードするなら頂点よりも辺が主役なので
    for _ in range(M):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        edges.append((a, b, c))
    """
    辺の重みを正負逆転させることで単一始点最短経路問題を解けば良い。
    ベルマンフォードで負閉路を検出したら"inf"を返す。
    ABC137Eを参考にする。
    """
    d = [10**18] * N
    d[0] = 0
    step = 0
    update = True
    while update:
        update = False
        for a, b, c in edges:
            new_cost = d[a] - c
            if new_cost < d[b]:
                update = True
                d[b] = new_cost
        step += 1
        if step > N:
            print("inf")
            return
    print(-d[N - 1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def bellman_ford(s):
    '''
    始点sから各頂点への最短距離を求める (重み付き有向グラフ)
    '''
    dist = [float('inf')] * v
    dist[s] = 0

    for i in range(v):
        update = False
        for p, q, cost in edge:
            if dist[p] != float('inf') and dist[q] > dist[p] + cost:
                dist[q] = dist[p] + cost
                update = True
        if not update:
            break
        if i == v - 1:
            return False

    return dist


v, e = map(int, input().split())

edge = []
for _ in range(e):
    s, t, d = map(int, input().split())
    edge.append([s-1, t-1, -d])

res = bellman_ford(0)

if not res:
    print('inf')
else:
    print(-res[-1])

Submission status: Wrong Answer

Solution code:
def bellman_ford(s):
    '''
    始点sから各頂点への最短距離を求める (重み付き有向グラフ)
    '''
    d = [float('inf')] * v
    d[s] = 0

    for i in range(v):
        update = False
        for p, q, cost in edge:
            if d[p] != float('inf') and d[q] > d[p] + cost:
                d[q] = d[p] + cost
                update = True
        if not update:
            break
        if i == v - 1:
            return False

    return d


v, e = map(int, input().split())

edge = []
for _ in range(e):
    s, t, d = map(int, input().split())
    edge.append([s-1, t-1, -d])

res = bellman_ford(0)

if not res:
    print('inf')
else:
    print(-res[-1])

Submission status: Wrong Answer

Solution code:
def bellman_ford(s):
    '''
    始点sから各頂点への最短距離を求める (重み付き有向グラフ)
    '''
    d = [float("inf")] * v
    d[s] = 0

    for i in range(v):
        update = False
        for p, q, cost in edge:
            if d[p] != float('inf') and d[q] > d[p] + cost:
                d[q] = d[p] + cost
                update = True
        if not update:
            break
        if i == v - 1:
            return False

    return d


v, e = map(int, input().split())

edge = []
for _ in range(e):
    s, t, d = map(int, input().split())
    edge.append([s-1, t-1, -d])

res = bellman_ford(0)

if not res:
    print('inf')
else:
    print(-res[-1])

Submission status: Wrong Answer

Solution code:
def bellman_ford(s):
    '''
    始点sから各頂点への最短距離を求める (重み付き有向グラフ)
    '''
    d = [float("inf")] * v
    d[s] = 0

    for i in range(v):
        update = False
        for p, q, cost in edge:
            if d[p] != float('inf') and d[q] > d[p] + cost:
                d[q] = d[p] + cost
                update = True
        if not update:
            break
        if i == v - 1:
            return False

    return d


v, e = map(int, input().split())

edge = []
for _ in range(e):
    s, t, d = map(int, input().split())
    edge.append([s-1, t-1, -d])

res = bellman_ford(0)

if not res:
    print('INF')
else:
    print(-res[-1])

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
from collections import defaultdict
G = defaultdict(dict)
for i in range(1,n):
    G[i+1] = {}
for i in range(m):
    a,b,c = map(int, input().split())
    G[a][b] = c
start_vertex = 1
def bellmanford(G, start_vertex):
    if start_vertex not in G:
        return -1, -1
    distances = {}
    parents   = {}
    for node in G:
        distances[node] = float('-inf')
        parents[node]   = None
    distances[start_vertex] = 0
    for _ in range(len(G)-1):
        for node in G.keys():
            for neighbor in G[node]:
                if distances[neighbor] < distances[node] + G[node][neighbor]:
                    distances[neighbor] = distances[node] + G[node][neighbor]
                    parents[neighbor]   = node
    for node in G.keys():
        for neighbor in G[node]:
            if distances[neighbor] < distances[node] + G[node][neighbor]:
                print('inf' , flush=True)
                return -1,-1
    return distances, parents
distances, parents = bellmanford(G, start_vertex)
if distances != -1:
    print(distances[n] , flush=True)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
from collections import defaultdict
G = defaultdict(dict)
for i in range(1,n):
    G[i+1] = {}
for i in range(m):
    a,b,c = map(int, input().split())
    G[a][b] = c
start_vertex = 1
def bellmanford(G, start_vertex):
    if start_vertex not in G:
        return -1, -1
    distances = {}
    parents   = {}
    for node in G:
        distances[node] = float('-inf')
        parents[node]   = None
    distances[start_vertex] = 0
    for _ in range(len(G)):
        for node in G.keys():
            for neighbor in G[node]:
                if distances[neighbor] < distances[node] + G[node][neighbor]:
                    distances[neighbor] = distances[node] + G[node][neighbor]
                    parents[neighbor]   = node
    for node in G.keys():
        for neighbor in G[node]:
            if distances[neighbor] < distances[node] + G[node][neighbor]:
                print('inf' , flush=True)
                return -1,-1
            if node == n:
                if node in G[neighbor]:
                    if G[node][neighbor] + G[neighbor][node] > 0:
                        print('inf' , flush=True)
                        return -1,-1
    return distances, parents
distances, parents = bellmanford(G, start_vertex)
if distances != -1:
    print(distances[n] , flush=True)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
from collections import defaultdict
G = defaultdict(dict)
for i in range(1,n):
    G[i+1] = {}
for i in range(m):
    a,b,c = map(int, input().split())
    G[a][b] = c
start_vertex = 1
def bellmanford(G, start_vertex):
    if start_vertex not in G:
        return -1, -1
    distances = {}
    parents   = {}
    for node in G:
        distances[node] = float('-inf')
        parents[node]   = None
    distances[start_vertex] = 0
    for _ in range(len(G)):
        for node in G.keys():
            for neighbor in G[node]:
                if distances[neighbor] < distances[node] + G[node][neighbor]:
                    distances[neighbor] = distances[node] + G[node][neighbor]
                    parents[neighbor]   = node
    for node in G.keys():
        for neighbor in G[node]:
            if (distances[neighbor] < distances[node] + G[node][neighbor]):
                print('inf' , flush=True)
                return -1,-1
    return distances, parents
distances, parents = bellmanford(G, start_vertex)
if distances != -1:
    print(distances[n] , flush=True)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
from collections import defaultdict
G = defaultdict(dict)
for i in range(n):
    G[i+1] = {}
for i in range(m):
    a,b,c = map(int, input().split())
    G[a][b] = c
start_vertex = 1
def bellmanford(G, start_vertex):
    if start_vertex not in G:
        return -1, -1
    distances = {}
    parents   = {}
    for node in G:
        distances[node] = float('-inf')
        parents[node]   = None
    distances[start_vertex] = 0
    for _ in range(len(G)):
        for node in G.keys():
            for neighbor in G[node]:
                if distances[neighbor] < distances[node] + G[node][neighbor]:
                    distances[neighbor] = distances[node] + G[node][neighbor]
                    parents[neighbor]   = node
    for node in G.keys():
        for neighbor in G[node]:
            if (distances[neighbor] < distances[node] + G[node][neighbor]):
                print('inf' , flush=True)
                return -1,-1
    return distances, parents
distances, parents = bellmanford(G, start_vertex)
if distances != -1:
    print(distances[n] , flush=True)

Submission status: Wrong Answer

Solution code:
INF = 10e10

def bellmanford(n,m,l):
    d = [-INF for i in range(n)]
    d[0] = 0
    for loop in range(2):
        updated = False
        for k in range(n+1):
            for abc in l:
                if d[abc[0]-1] > -INF:
                    if d[abc[1]-1] < d[abc[0]-1] + abc[2]:
                        d[abc[1]-1] = d[abc[0]-1] + abc[2]
                        if abc[1] == n:
                            updated = True
        if not updated:
            return d[n-1]
        if loop == 1:
            return 'inf'
        if d[n-1] <= 0:
            return d[n-1]

def main():
    n,m = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(m)]
    
    print(bellmanford(n,m,l))
    
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
INF = 10e10

def bellmanford(n,m,l):
    d = [-INF for i in range(n)]
    d[0] = 0
    for loop in range(2):
        updated = False
        for k in range(n+1):
            for abc in l:
                if d[abc[0]-1] > -INF:
                    if d[abc[1]-1] < d[abc[0]-1] + abc[2]:
                        d[abc[1]-1] = d[abc[0]-1] + abc[2]
                        if abc[1] == n:
                            updated = True
        if not updated:
            return d[n-1]
        if loop == 1:
            return 'inf'
        if d[n-1] < 0:
            return d[n-1]

def main():
    n,m = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(m)]
    
    print(bellmanford(n,m,l))
    
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
sc=0
for _ in range(m):
  a,b,c=map(int,input().split())
  e[a]+=[(b,c)]
  sc+=max(c,0)
q=[1]
vis=[-10**18]*(n+1)
vis[1]=0
while q:
  now=q.pop()
  for to,cost in e[now]:
    q+=[to]
    vis[to]=max(vis[now]+cost,vis[to])
  if vis[now]>sc:
    print('inf')
    exit()
print(vis[n])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
e=[[] for _ in range(n+1)]
for _ in range(m):
  a,b,c=map(int,input().split())
  e[a]+=[(b,c)]
for i in range(n+1):
  q=[i]
  vis=[1]*(n+1)
  while q:
    now=q.pop()
    for to,cost in e[now]:
      if vis[to]:
        q+=[to]
        vis[to]=0
        if to==i:
          print('inf')
          exit()
q=[1]
vis=[-10**18]*(n+1)
vis[1]=0
while q:
  now=q.pop()
  for to,cost in e[now]:
    q+=[to]
    vis[to]=max(vis[now]+cost,vis[to])
print(vis[n])