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:
#coding=UTF-8

#ゴールに関係無い袋小路で永パされると、探索が収束しない
#かつ答えがinfでないということで 修正

#表にあるかを尋ねるのが重いので
#データ構造を変えて回避する
mozir=input()
hyo=mozir.split(' ')

N=int(hyo[0])
M=int(hyo[1])

#idx番目の都市に繋っている道とコストのタプルを持つリスト
tuuro=[]
# [] はコピーがしんどいものだったりするので
# 参照でごまかしたりしてくる
# なので1個づつ書いている
for idx in range(0,N,1):
    tuuro.append([])


A=[]
B=[]

for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    tuuro[int(hyo[0])-1].append((int(hyo[1])-1,int(hyo[2])))

#print(tuuro)
#普通の経路探索のようなことをする
#永パ
tmp_score=[None]*N #マイナス点のときもある
tmp_score[0]=0
tansaku=[0]
loopconut=0
while len(tansaku) > 0:
    loopconut=loopconut+1
    next_tansaku=[]
    for mono in tansaku:
        for deru in tuuro[mono]:
            kouho_ten=tmp_score[mono]+deru[1]
            if tmp_score[deru[0]] == None or kouho_ten > tmp_score[deru[0]]:
                tmp_score[deru[0]]=kouho_ten
                next_tansaku.append(deru[0])

    tansaku=list(set(next_tansaku))
    if loopconut==N+3:
        tmp_ans=tmp_score[N-1] #cannot be None
    elif loopconut==3*N:
        if tmp_score[N-1] > tmp_ans:
            print('inf')
            break
        else:
            #関係の無い無限ループ
            print(tmp_score[N-1])
            break
else:
    print(tmp_score[N-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def set_enable_goal(cur_node, back_paths, enable_goal):
    if cur_node in back_paths:
        for next_node in back_paths[cur_node]:
            if enable_goal[next_node - 1] == 0:
                enable_goal[next_node - 1] = 1
                set_enable_goal(next_node, back_paths, enable_goal)


N, M = map(int, input().split())
MIN = float('-inf')
INF_LIMIT = -MIN

back_paths = {}
all_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in all_paths:
        all_paths[a].append((b, c))
    else:
        all_paths[a] = [(b, c)]

    if b in back_paths:
        back_paths[b].append(a)
    else:
        back_paths[b] = [a]


# path cut
enable_goal= [0 for i in range(N)]
enable_goal[N - 1] = 1
set_enable_goal(N, back_paths, enable_goal)

for a, paths in all_paths.items():
    if not enable_goal[a - 1]:
        all_paths[a] = []
    else:
        valid_paths = []
        for b, c in paths:
            if enable_goal[b - 1]:
                valid_paths.append((b, c))
        all_paths[a] = valid_paths


scores = [MIN for i in range(N)]
scores[0] = 0

is_inf = False
for n in range(N):
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)

# loop check
if not is_inf:
    prev_score = scores[N - 1]
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)
#    if prev_score != scores[N - 1]:
#        is_inf = True


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def set_enable_goal(cur_node, back_paths, enable_goal):
    if cur_node in back_paths:
        for next_node in back_paths[cur_node]:
            if enable_goal[next_node - 1] == 0:
                enable_goal[next_node - 1] = 1
                set_enable_goal(next_node, back_paths, enable_goal)


N, M = map(int, input().split())
MIN = float('-inf')
INF_LIMIT = -MIN

back_paths = {}
all_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in all_paths:
        all_paths[a].append((b, c))
    else:
        all_paths[a] = [(b, c)]

    if b in back_paths:
        back_paths[b].append(a)
    else:
        back_paths[b] = [a]


# path cut
enable_goal= [0 for i in range(N)]
enable_goal[N - 1] = 1
set_enable_goal(N, back_paths, enable_goal)

for a, paths in all_paths.items():
    if not enable_goal[a - 1]:
        all_paths[a] = []
    else:
        valid_paths = []
        for b, c in paths:
            if enable_goal[b - 1]:
                valid_paths.append((b, c))
        all_paths[a] = valid_paths


scores = [MIN for i in range(N)]
scores[0] = 0

is_inf = False
for n in range(N):
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)

# loop check
if not is_inf:
    prev_score = scores[N - 1]
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)
    if prev_score != scores[N - 1]:
        is_inf = True


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def set_enable_goal(cur_node, back_paths, enable_goal):
    if cur_node in back_paths:
        for next_node in back_paths[cur_node]:
            if enable_goal[next_node - 1] == 0:
                enable_goal[next_node - 1] = 1
                set_enable_goal(next_node, back_paths, enable_goal)


N, M = map(int, input().split())
MIN = float('-inf')
INF_LIMIT = -MIN

back_paths = {}
all_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in all_paths:
        all_paths[a].append((b, c))
    else:
        all_paths[a] = [(b, c)]

'''
    if b in back_paths:
        back_paths[b].append(a)
    else:
        back_paths[b] = [a]


# path cut
enable_goal= [0 for i in range(N)]
enable_goal[N - 1] = 1
set_enable_goal(N, back_paths, enable_goal)

for a, paths in all_paths.items():
    if not enable_goal[a - 1]:
        all_paths[a] = []
    else:
        valid_paths = []
        for b, c in paths:
            if enable_goal[b - 1]:
                valid_paths.append((b, c))
        all_paths[a] = valid_paths
'''


scores = [MIN for i in range(N)]
scores[0] = 0

is_inf = False
for n in range(N):
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                if scores[a - 1] + c > INF_LIMIT or scores[a - 1] + c < -INF_LIMIT:
                    is_inf = True
                    break
                else:
                    scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)

# loop check
if not is_inf:
    prev_scores = list(scores)
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)
    for p, s in zip(prev_scores, scores):
        if p != s:
            is_inf = True
            break

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def set_enable_goal(cur_node, back_paths, enable_goal):
    if cur_node in back_paths:
        for next_node in back_paths[cur_node]:
            if enable_goal[next_node - 1] == 0:
                enable_goal[next_node - 1] = 1
                set_enable_goal(next_node, back_paths, enable_goal)


N, M = map(int, input().split())
MIN = float('-inf')
INF_LIMIT = -MIN

back_paths = {}
all_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if b in back_paths:
        back_paths[b].append(a)
    else:
        back_paths[b] = [a]

    if a in all_paths:
        all_paths[a].append((b, c))
    else:
        all_paths[a] = [(b, c)]

enable_goal= [0 for i in range(N)]
enable_goal[N - 1] = 1
set_enable_goal(N, back_paths, enable_goal)

for a, paths in all_paths.items():
    if not enable_goal[a - 1]:
        all_paths[a] = []
    else:
        valid_paths = []
        for b, c in paths:
            if enable_goal[b - 1]:
                valid_paths.append((b, c))
        all_paths[a] = valid_paths


scores = [MIN for i in range(N)]
scores[0] = 0

is_inf = False
for n in range(N):
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                if scores[a - 1] + c > INF_LIMIT or scores[a - 1] + c < -INF_LIMIT:
                    is_inf = True
                    break
                else:
                    scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)

# loop check
if not is_inf:
    prev_scores = list(scores)
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)
    for p, s in zip(prev_scores, scores):
        if p != s:
            is_inf = True
            break

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def set_enable_goal(cur_node, back_paths, enable_goal):
    if cur_node in back_paths:
        for next_node in back_paths[cur_node]:
            if enable_goal[next_node - 1] == 0:
                enable_goal[next_node - 1] = 1
                set_enable_goal(next_node, back_paths, enable_goal)


N, M = map(int, input().split())
MIN = float('-inf')
INF_LIMIT = 24000000000

back_paths = {}
all_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if b in back_paths:
        back_paths[b].append(a)
    else:
        back_paths[b] = [a]

    if a in all_paths:
        all_paths[a].append((b, c))
    else:
        all_paths[a] = [(b, c)]

enable_goal= [0 for i in range(N)]
enable_goal[N - 1] = 1
set_enable_goal(N, back_paths, enable_goal)

for a, paths in all_paths.items():
    if not enable_goal[a - 1]:
        all_paths[a] = []
    else:
        valid_paths = []
        for b, c in paths:
            if enable_goal[b - 1]:
                valid_paths.append((b, c))
        all_paths[a] = valid_paths


scores = [MIN for i in range(N)]
scores[0] = 0

is_inf = False
for n in range(N):
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                if scores[a - 1] + c > INF_LIMIT or scores[a - 1] + c < -INF_LIMIT:
                    is_inf = True
                    break
                else:
                    scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)

# loop check
if not is_inf:
    prev_scores = list(scores)
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)
    for p, s in zip(prev_scores, scores):
        if p != s:
            is_inf = True
            break

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

Submission status: Wrong Answer

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

import sys
import os
import math

N, M = map(int, input().split())
#print('N', N)
#print('M', M)

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

# 始点から到達不可能な頂点は除去する
visited = [False] * N
Q = [0]
while Q:
    i = Q.pop(0)
    visited[i] = True
    for edge in A[i]:
        to = edge[0]
        if not visited[to]:
            Q.append(to)
# 到達不可能な頂点
unreachable = []
reachable = []
for i in range(N):
    if visited[i]:
        reachable.append(i)
    else:
        unreachable.append(i)
#print('unreach', unreachable)
#for i in unreachable:
#    A[i] = []

dists = [float('inf')] * N
dists[0] = 0
def bellman_ford(A):
    for i in range(N):
        for v in reachable:
            for edge in A[v]:
                to = edge[0]
                cost = edge[1]
                if dists[v] != float('inf') and dists[to] > dists[v] + cost:
                    dists[to] = dists[v] + cost
                    if i == N - 1:
                        return True
    return False

is_loop = bellman_ford(A)

if is_loop:
    print('inf')
else:
    if dists[N-1] == float('inf'):
        print('inf')
    else:
        print(-dists[N-1])

Submission status: Wrong Answer

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

import sys
import os
import math

N, M = map(int, input().split())
#print('N', N)
#print('M', M)

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

# 始点から到達不可能な頂点は除去する
visited = [False] * N
Q = [0]
while Q:
    i = Q.pop(0)
    visited[i] = True
    for edge in A[i]:
        to = edge[0]
        if not visited[to]:
            Q.append(to)
# 到達不可能な頂点
unreachable = []
reachable = []
for i in range(N):
    if visited[i]:
        reachable.append(i)
    else:
        unreachable.append(i)
#print('unreach', unreachable)
#for i in unreachable:
#    A[i] = []

dists = [float('inf')] * N
dists[0] = 0
def bellman_ford(A):
    for i in range(N):
        for v in reachable:
            for edge in A[v]:
                to = edge[0]
                cost = edge[1]
                if dists[v] != float('inf') and dists[to] > dists[v] + cost:
                    dists[to] = dists[v] + cost
                    if i == N - 1:
                        return True
    return False

is_loop = bellman_ford(A)

if is_loop:
    print('inf')
else:
    dists_copy = dists[:]
    bellman_ford(A)
    if dists == dists_copy:
        print(-dists[N-1])
    else:
        print('inf')

Submission status: Wrong Answer

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

import sys
import os
import math

N, M = map(int, input().split())
#print('N', N)
#print('M', M)

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

# 始点から到達不可能な頂点は除去する
visited = [False] * N
Q = [0]
while Q:
    i = Q.pop(0)
    visited[i] = True
    for edge in A[i]:
        to = edge[0]
        if not visited[to]:
            Q.append(to)
# 到達不可能な頂点
unreachable = []
reachable = []
for i in range(N):
    if visited[i]:
        reachable.append(i)
    else:
        unreachable.append(i)
#print('unreach', unreachable)
#for i in unreachable:
#    A[i] = []

dists = [float('inf')] * N
dists[0] = 0
def bellman_ford(A):
    is_loop = False
    for i in range(N):
        for v in reachable:
            for edge in A[v]:
                to = edge[0]
                cost = edge[1]
                if dists[v] != float('inf') and dists[to] > dists[v] + cost:
                    dists[to] = dists[v] + cost
                    if i == N - 1:
                        is_loop = True
    return is_loop

is_loop = bellman_ford(A)

if is_loop:
    print('inf')
else:
    # パスがある
    print(-dists[N-1])

Submission status: Wrong Answer

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

import sys
import os
import math

N, M = map(int, input().split())
#print('N', N)
#print('M', M)

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

# 始点から到達不可能な頂点は除去する
visited = [False] * N
Q = [0]
while Q:
    i = Q.pop(0)
    visited[i] = True
    for edge in A[i]:
        to = edge[0]
        if not visited[to]:
            Q.append(to)
# 到達不可能な頂点
unreachable = []
reachable = []
for i in range(N):
    if visited[i]:
        reachable.append(i)
    else:
        unreachable.append(i)
#print('unreach', unreachable)
#for i in unreachable:
#    A[i] = []

dists = [float('inf')] * N
dists[0] = 0
def bellman_ford(A):
    for i in range(N):
        for v in reachable:
            for edge in A[v]:
                to = edge[0]
                cost = edge[1]
                if dists[v] != float('inf') and dists[to] > dists[v] + cost:
                    dists[to] = dists[v] + cost
                    if i == N - 1:
                        return True
    return False

is_loop = bellman_ford(A)

if is_loop:
    print('inf')
else:
    # パスがある
    print(-dists[N-1])

Submission status: Wrong Answer

Solution code:
#coding=UTF-8

#表にあるかを尋ねるのが重いので
#データ構造を変えて回避する
mozir=input()
hyo=mozir.split(' ')

N=int(hyo[0])
M=int(hyo[1])

#idx番目の都市に繋っている道とコストのタプルを持つリスト
tuuro=[]
# [] はコピーがしんどいものだったりするので
# 参照でごまかしたりしてくる
# なので1こづつ書いている
for idx in range(0,N,1):
    tuuro.append([])


A=[]
B=[]

for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    tuuro[int(hyo[0])-1].append((int(hyo[1])-1,int(hyo[2])))

#print(tuuro)
#普通の経路探索のようなことをする
#永パ
tmp_score=[None]*N #マイナス点のときもある
tmp_score[0]=0
tansaku=[0]
loopconut=0
while len(tansaku) > 0:
    loopconut=loopconut+1
    next_tansaku=[]
    for mono in tansaku:
        for deru in tuuro[mono]:
            kouho_ten=tmp_score[mono]+deru[1]
            if tmp_score[deru[0]] == None or kouho_ten > tmp_score[deru[0]]:
                tmp_score[deru[0]]=kouho_ten
                next_tansaku.append(deru[0])

    tansaku=list(set(next_tansaku))
    if loopconut > 2*N+1:
        #鳩の巣原理で訪れる都市が重複している
        #直線になっているパターンでは、loopconut==Nでtansaku==[]
        #なのでもう1個回す必要がある
        print('inf')
        break
else:
    print(tmp_score[N-1])

Submission status: Wrong Answer

Solution code:
#coding=UTF-8

#表にあるかを尋ねるのが重いので
#データ構造を変えて回避する
mozir=input()
hyo=mozir.split(' ')

N=int(hyo[0])
M=int(hyo[1])

#idx番目の都市に繋っている道とコストのタプルを持つリスト
tuuro=[]
# [] はコピーがしんどいものだったりするので
# 参照でごまかしたりしてくる
# なので1こづつ書いている
for idx in range(0,N,1):
    tuuro.append([])


A=[]
B=[]

for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    tuuro[int(hyo[0])-1].append((int(hyo[1])-1,int(hyo[2])))

#print(tuuro)
#普通の経路探索のようなことをする
#永パ
tmp_score=[None]*N #マイナス点のときもある
tmp_score[0]=0
tansaku=[0]
loopconut=0
while len(tansaku) > 0:
    loopconut=loopconut+1
    next_tansaku=[]
    for mono in tansaku:
        for deru in tuuro[mono]:
            kouho_ten=tmp_score[mono]+deru[1]
            if tmp_score[deru[0]] == None or kouho_ten > tmp_score[deru[0]]:
                tmp_score[deru[0]]=kouho_ten
                next_tansaku.append(deru[0])

    tansaku=list(set(next_tansaku))
    if loopconut > N:
        #鳩の巣原理で訪れる都市が重複している
        #直線になっているパターンでは、loopconut==Nでtansaku==[]
        #なのでもう1個回す必要がある
        print('inf')
        break
else:
    print(tmp_score[N-1])

Submission status: Wrong Answer

Solution code:
#coding=UTF-8


mozir=input()
hyo=mozir.split(' ')

N=int(hyo[0])
M=int(hyo[1])

A=[]
B=[]
Cost=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    A.append(int(hyo[0])-1)
    B.append(int(hyo[1])-1)
    Cost.append(int(hyo[2]))
    
#普通の経路探索のようなことをし、全エッジ数を越えても終了しないときは
#永パ
tmp_score=[None]*N #マイナス点のときもある
tmp_score[0]=0
tansaku=[0]
loopconut=0
while len(tansaku) > 0:
    loopconut=loopconut+1
    next_tansaku=[]
    for mono in tansaku:
        for idy in range(0,M,1):
            if A[idy]==mono:
                kouho_ten=tmp_score[mono]+Cost[idy]
                if tmp_score[B[idy]] == None or kouho_ten > tmp_score[B[idy]]:
                        tmp_score[B[idy]]=kouho_ten
                        next_tansaku.append(B[idy])

        tansaku=next_tansaku
    if loopconut > M+1: #経路を重複して使っているやつが出て来ている
        #直線になっているパターンでは、loopconut==M+1でtansaku==[]
        #なのでもう1個回す必要がある
        print('inf')
        break
else:
    print(tmp_score[N-1])

Submission status: Wrong Answer

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

import sys
import os
import math

N, M = map(int, input().split())
#print('N', N)
#print('M', M)

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

# 始点から到達不可能な頂点は除去する
visited = [False] * N
Q = [0]
while Q:
    i = Q.pop(0)
    visited[i] = True
    for edge in A[i]:
        to = edge[0]
        if not visited[to]:
            Q.append(to)
# 到達不可能な頂点
unreachable = []
reachable = []
for i in range(N):
    if visited[i]:
        reachable.append(i)
    else:
        unreachable.append(i)
#print('unreach', unreachable)
#for i in unreachable:
#    A[i] = []

dists = [float('inf')] * N
dists[0] = 0
def bellman_ford(A):
    for i in reachable:
        for v in reachable:
            for edge in A[v]:
                to = edge[0]
                cost = edge[1]
                if dists[v] != float('inf') and dists[to] > dists[v] + cost:
                    dists[to] = dists[v] + cost
                    if i == N - 1:
                        return True
    return False

is_loop = bellman_ford(A)

if is_loop:
    print('inf')
else:
    # パスがある
    print(-dists[N-1])

Submission status: Wrong Answer

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

import sys
import os
import math

N, M = map(int, input().split())
#print('N', N)
#print('M', M)

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

# 始点から到達不可能な頂点は除去する
visited = [False] * N
Q = [0]
while Q:
    i = Q.pop(0)
    visited[i] = True
    for edge in A[i]:
        to = edge[0]
        if not visited[to]:
            Q.append(to)
# 到達不可能な頂点
unreachable = []
reachable = []
for i in range(N):
    if visited[i]:
        reachable.append(i)
    else:
        unreachable.append(i)
#print('unreach', unreachable)
#for i in unreachable:
#    A[i] = []

dists = [float('inf')] * N
dists[0] = 0
def bellman_ford(A):
    for i in reachable:
        for v in reachable:
            for edge in A[v]:
                to = edge[0]
                if to in reachable:
                    cost = edge[1]
                    if dists[v] != float('inf') and dists[to] > dists[v] + cost:
                        dists[to] = dists[v] + cost
                        if i == N - 1:
                            return True
    return False

is_loop = bellman_ford(A)

if is_loop:
    print('inf')
else:
    # パスがある
    print(-dists[N-1])

Submission status: Wrong Answer

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

import sys
import os
import math

N, M = map(int, input().split())
#print('N', N)
#print('M', M)

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

# 始点から到達不可能な頂点は除去する
visited = [False] * N
Q = [0]
while Q:
    i = Q.pop(0)
    visited[i] = True
    for edge in A[i]:
        to = edge[0]
        if not visited[to]:
            Q.append(to)
# 到達不可能な頂点
unreachable = []
reachable = []
for i in range(N):
    if visited[i]:
        reachable.append(i)
    else:
        unreachable.append(i)
#print('unreach', unreachable)
for i in unreachable:
    A[i] = []

dists = [float('inf')] * N
dists[0] = 0
def bellman_ford(A):
    for i in reachable:
        for v in reachable:
            for edge in A[v]:
                to = edge[0]
                cost = edge[1]
                if dists[v] != float('inf') and dists[to] > dists[v] + cost:
                    dists[to] = dists[v] + cost
                    if i == N - 1:
                        return True
    return False

is_loop = bellman_ford(A)

if is_loop:
    print('inf')
else:
    # パスがある
    print(-dists[N-1])

Submission status: Wrong Answer

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

import sys
import os
import math

N, M = map(int, input().split())
#print('N', N)
#print('M', M)

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

# 始点から到達不可能な頂点は除去する
visited = [False] * N
Q = [0]
while Q:
    i = Q.pop(0)
    visited[i] = True
    for edge in A[i]:
        to = edge[0]
        if not visited[to]:
            Q.append(to)
# 到達不可能な頂点
unreachable = []
for i in range(N):
    if not visited[i]:
        unreachable.append(i)
#print('unreach', unreachable)
for i in unreachable:
    A[i] = []

dists = [float('inf')] * N
dists[0] = 0
def bellman_ford(A):
    for i in range(N):
        for v in range(N):
            for edge in A[v]:
                to = edge[0]
                cost = edge[1]
                if dists[v] != float('inf') and dists[to] > dists[v] + cost:
                    dists[to] = dists[v] + cost
                    if i == N - 1:
                        return True
    return False

is_loop = bellman_ford(A)

if is_loop:
    print('inf')
else:
    # パスがある
    print(-dists[N-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
abc = [list(map(int, input().split())) for x in range(m)]
 
nodemap = [[] for x in range(n + 1)]
 
for a, b, c in abc:
    nodemap[a].append([a, b, c])

changed = False

calced = [-(10**10) for x in range(n + 1)]
calced[1] = 0

for i in range(n + 1):
    changed = False
    for nodes in nodemap:
        for node in nodes:
            now, nextnode, addvalue = node
            if calced[nextnode] < calced[now] + addvalue:
                calced[nextnode] = calced[now] + addvalue
                changed = True
print("inf" if changed else calced[n])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
abc = [list(map(int, input().split())) for x in range(m)]
 
nodemap = [[] for x in range(n + 1)]
 
for a, b, c in abc:
    nodemap[a].append([a, b, c])

changed = False

calced = [-(10**10) for x in range(n + 1)]
calced[1] = 0

for i in range(n):
    changed = False
    for nodes in nodemap:
        for node in nodes:
            now, nextnode, addvalue = node
            if calced[nextnode] < calced[now] + addvalue:
                calced[nextnode] = calced[now] + addvalue
                changed = True
print("inf" if changed else calced[n])

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]*N# iに到達するときの最大得点
moji=[1]+[0]*(N-1)#infなら0をかえす
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji[b[m]-1]=1
 
moji2=[0]*N
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
        moji2[b[m]-1]=1
    if moji2[a[m]-1]:
      moji2[b[m]-1]=1
if moji2[N-1]:
  print("inf")
else:
  print(V[N-1])

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]*N# iに到達するときの最大得点
moji=[1]+[0]*(N-1)#infなら0をかえす
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji[b[m]-1]=1
 
moji2=[0]*N
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=W[a[m]-1]+c[m]
        moji2[b[m]-1]=1
    if moji2[a[m]-1]:
      moji2[b[m]-1]=1
if moji2[N-1]:
  print("inf")
else:
  print(V[N-1])

Submission status: Wrong Answer

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

import sys
import os
import math

N, M = map(int, input().split())
#print('N', N)
#print('M', M)

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

dists = [float('inf')] * N
dists[0] = 0
def bellman_ford(A):
    for i in range(N):
        for v in range(N):
            for edge in A[v]:
                to = edge[0]
                cost = edge[1]
                if dists[v] != float('inf') and dists[to] > dists[v] + cost:
                    dists[to] = dists[v] + cost
                    if i == N - 1:
                        return True
    return False

res = bellman_ford(A)
dists_copy = dists[:]
res = bellman_ford(A)

if dists != dists_copy:
    print('inf')
elif res == True:
    print('inf')
else:
    # パスがある
    print(-dists[N-1])

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]*N# iに到達するときの最大得点
moji=[1]+[0]*(N-1)#infなら0をかえす
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji[b[m]-1]=1
 
moji2=[0]*N
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=W[a[m]-1]+c[m]
        moji2[b[m]-1]=1
    if moji2[a[m]-1]:
      moji2[b[m]-1]
if moji2[N-1]:
  print("inf")
else:
  print(V[N-1])

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]*N# iに到達するときの最大得点
moji=[1]+[0]*(N-1)#infなら0をかえす
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji[b[m]-1]=1
 
W=[0]*N
moji=[0]*(N-1)+[1]
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        W[b[m]-1]=max(W[b[m]-1],W[a[m]-1]+c[m])
      else:
        W[b[m]-1]=W[a[m]-1]+c[m]
        moji[b[m]-1]=1
if W[N-1]>0 and moji[0]:
  print("inf")
else:
  print(V[N-1])

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]*N# iに到達するときの最大得点
moji=[1]+[0]*(N-1)#infなら0をかえす
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji[b[m]-1]=1
 
W=[0]*N
moji=[0]*(N-1)+[1]
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        W[b[m]-1]=max(W[b[m]-1],W[a[m]-1]+c[m])
      else:
        W[b[m]-1]=W[a[m]-1]+c[m]
        moji[b[m]-1]=1
if W[N-1]<=0 and moji[0]:
  print(V[N-1])
else:
  print("inf")