Problem:


Score : 500 points

Problem Statement

There is a directed graph with N vertices numbered 1 to N and M edges.
The i-th edge is directed from Vertex A_i to Vertex B_i, and there are C_i coins placed along that edge.
Additionally, there is a button on Vertex N.

We will play a game on this graph.
You start the game on Vertex 1 with zero coins, and head for Vertex N by traversing the edges while collecting coins.
It takes one minute to traverse an edge, and you can collect the coins placed along the edge each time you traverse it.
As usual in games, even if you traverse an edge once and collect the coins, the same number of coins will reappear next time you traverse that edge, which you can collect again.

When you reach Vertex N, you can end the game by pressing the button. (You can also choose to leave Vertex N without pressing the button and continue traveling.)
However, when you end the game, you will be asked to pay T \times P coins, where T is the number of minutes elapsed since the start of the game. If you have less than T \times P coins, you will have to pay all of your coins instead.

Your score will be the number of coins you have after this payment.
Determine if there exists a maximum value of the score that can be obtained. If the answer is yes, find that maximum value.

Constraints

2 \leq N \leq 2500

1 \leq M \leq 5000

1 \leq A_i, B_i \leq N

1 \leq C_i \leq 10^5

0 \leq P \leq 10^5

All values in input are integers.

Vertex N can be reached from Vertex 1.

Input

Input is given from Standard Input in the following format:

N M P
A_1 B_1 C_1
:
A_M B_M C_M

Output

If there exists a maximum value of the score that can be obtained, print that maximum value; otherwise, print -1.

Sample Input 1

3 3 10
1 2 20
2 3 30
1 3 45

Sample Output 1

35

There are two ways to travel from Vertex 1 to Vertex 3:

Vertex 1 \rightarrow 2 \rightarrow 3: You collect 20 + 30 = 50 coins on the way. After two minutes from the start of the game, you press the button, pay 2 \times 10 = 20 coins, and you have 50 - 20 = 30 coins left.

Vertex 1 \rightarrow 2: You collect 45 coins on the way. After one minute from the start of the game, you press the button, pay 1 \times 10 = 10 coins, and you have 45 - 10 = 35 coins left.

Thus, the maximum score that can be obtained is 35.

Sample Input 2

2 2 10
1 2 100
2 2 100

Sample Output 2

-1

The edge extending from Vertex 1 takes you to Vertex 2. If you then traverse the edge extending from Vertex 2 to itself t times and press the button, your score will be 90 + 90t. Thus, you can infinitely increase your score, which means there is no maximum value of the score that can be obtained.

Sample Input 3

4 5 10
1 2 1
1 4 1
3 4 1
2 2 100
3 3 100

Sample Output 3

0

There is no way to travel from Vertex 1 to Vertex 4 other than traversing the edge leading from Vertex 1 to Vertex 4 directly. You will pick up one coin along this edge, but after being asked to paying 10 coins, your score will be 0.

Note that you can collect an infinite number of coins if you traverse the edge leading from Vertex 1 to Vertex 2, but this is pointless since you can no longer reach Vertex 4 and end the game.



Sample input:
3 3 10
1 2 20
2 3 30
1 3 45


Sample output:
35

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7
from collections import deque

def main():
    N, M = iip(False)
    A = []
    for i in range(N):
        A.append(iip(True))

    ret = solve(N, M, A)
    print(ret)

def solve(N, M, A):
    A = sorted(A, key=lambda x:x[1], reverse=True)

    sch = [False] * M

    ret = 0
    for nouki, money in A:
        day = M - nouki
        if day < 0:
            continue

        do = True
        while True:
            print(day)
            if sch[day]:
                day -= 1
            else:
                break
            if day == -1:
                do = False
                break
        if not do:
            continue

        sch[day] = True
        ret += money

        #print(nouki, money)

    return ret




#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        #print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M, P = lr()
# 終了時、T*P枚支払う
graph = [tuplr(lr()) for _ in range(M)]

def bellmanford(start, N):
    INF = 10 ** 12
    dist = [-INF] * (N+1) # 1-indexed
    dist[start] = 0
    for i in range(N+N+5):
        for pre, ne, weight in graph:
            if dist[pre] != -INF and dist[pre] + weight - P > dist[ne]:
                dist[ne] = dist[pre] + weight - P
                # n回繰り返してもスコアが更新された場合
                if i > N-1:
                    dist[ne] = INF
    if dist[N] == INF:
        return -1
    else:
        return max(0, dist[N])

answer = bellmanford(1, N)
print(answer)

Submission status: Runtime Error

Solution code:
class BellmanFord:
  def __init__(self, n, edge):
    self.edge = edge
    self.n = n
    self.dist = [float('inf')] * self.n

  def fit(self):
    self.dist[0] = 0
    for _ in range(self.n - 1):
      for source, destination, weight in self.edge:
        tmp = self.dist[source] + weight
        if self.dist[destination] > tmp:
          self.dist[destination] = tmp
          self.prev[destination] = source

n, m, p = map(int, input().split())
edge = []
for _ in range(m):
  a, b, c = map(int, input().split())
  edge.append((a-1, b-1, p-c))
  
bf = BellmanFord(n, edge)
bf.run()
print(-min(0, bf.dist[-1]))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, M, P = map(int,input().split())
es = []
to = defaultdict(list)
rto = defaultdict(list)
rf = [False]*N
rt = [False]*N
for i in range(M):
  a, b, c = map(int, input().split())
  es += [(a-1,b-1,-c+P)]
  to[a-1] += [b-1]
  rto[b-1] += [a-1]

def dfs(v):
  if rf[v]:
    return
  rf[v] = True
  for u in to[v]:
    dfs(u)

def rdfs(v):
  if rt[v]:
    return
  rt[v] = True
  for u in rto[v]:
    rdfs(u)

dfs(0)
rdfs(N-1)
ok = [False]*N
for i in range(N):
  ok[i] = rf[i]&rt[i]

dist = [float('inf')]*N
dist[0] = 0
upd = True
cnt = 0
while upd:
  upd = False
  for j in range(M):
    f, t, c = es[j]
    if (not ok[f]) or (not ok[t]):
      continue
    if dist[t]>dist[f]+c:
      upd = True
      dist[t] = dist[f]+c
  cnt += 1
  if cnt>N:
    print(-1)
    break
else:
  print(max(0,-dist[N-1]))

Submission status: Runtime Error

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


def main():
    N, M, P = map(int, input().split())
    A, B, C = [0] * M, [0] * M, [0] * M
    v = [set() for _ in range(N)]
    u = [set() for _ in range(N)]
    for i in range(M):
        a, b, c = map(int, input().split())
        A[i], B[i], C[i] = a - 1, b - 1, P - c
        u[a - 1].add(b - 1)
        v[b - 1].add(a - 1)
    vv = set()
    cur = set([N - 1])
    while cur:
        vv |= cur
        cur = set().union(*(v[c] for c in cur)) - vv
    uu = set()
    cur = set([0])
    while cur:
        uu |= cur
        cur = set().union(*(u[c] for c in cur)) - uu
    reachable = vv & uu
    for i in range(M):
        if A[i] not in reachable or B[i] not in reachable:
            C[i] = 10 ** 9

    mx = csr_matrix((C, (A, B)), shape=(M, M))
    try:
        dm = bellman_ford(mx, indices=list(reachable))
    except NegativeCycleError:
        return -1
    return max(0, -int(dm[0][N - 1]))


print(main())

Submission status: Runtime Error

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


def main():
    N, M, P = map(int, input().split())
    A, B, C = [0] * M, [0] * M, [0] * M
    for i in range(M):
        a, b, c = map(int, input().split())
        A[i], B[i], C[i] = a - 1, b - 1, P - c
    mx = csr_matrix((C, (A, B)), shape=(M, M))
    try:
        dm = bellman_ford(mx, indices=[N - 1])
    except NegativeCycleError:
        return -1
    return max(0, -int(dm[0][N - 1]))


print(main())

Submission status: Runtime Error

Solution code:
import sys
import math
import heapq
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M,P=LI()
EDGES = []
EDGES2 = [[] for i in range(N+1)]
VISITED = [False]*(N+1)
LOOP = [False]*(N+1)
OK = [False]*(N+1)
OK[N] = True
VISITED[1]=True
DIST=[10**15]*(N+1)
DIST[1] = 0

for i in range(M):
    F,T,C=LI()
    EDGES.append((F,T,P-C))
    EDGES2[F].append(T)

for i in range(1,N+1):
    for j in range(M):
        fr, to, cost = EDGES[j]
        if (DIST[to] > DIST[fr] + cost):
            if (i == N):
                #         //頂点の数と同じ回数ループすると、負の閉路があるのでループをぬける
                # cout << "negative loop" << endl;
                # break
                LOOP[to] = True
                break
            else:
                DIST[to] = DIST[fr] + cost


def dfs(v=1):
    for i in EDGES[v]:
        if not VISITED[i]:
            VISITED[i] = True
            if i == N or dfs():
                OK[v] = True
                return True
    OK[v] = False
    return False
dfs()

for i in range(1, N+1):
    if LOOP[i] and OK[i]:
        print(-1)
        exit()

print(max(-DIST[-1],0))

Submission status: Runtime Error

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

class BellmanFord():
	def __init__(self, adj, start, size):
		self.adj = adj
		self.start = start
		self.size = size
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0

	def solve(self):
		for _ in range(self.size-1):
			for x in range(self.size):
				for y, w in self.adj[x]:
					if not s_reachable[x] or not s_reachable[y] or not g_reachable[x] or not g_reachable[y]:
						continue
					if self.dist[y] > self.dist[x] + w:
						self.dist[y] = self.dist[x] + w
		for x in range(self.size):
			for y, w in self.adj[x]:
				if not s_reachable[x] or not s_reachable[y] or not g_reachable[x] or not g_reachable[y]:
					continue
				if self.dist[y] > self.dist[x] + w:
					self.dist[y] = -10**30

		return

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

n, m, p = map(int, input().split())
adj = [[] for _ in range(n)]
adj_rev = [[] for _ in range(n)]

for _ in range(m):
	a, b, c = map(int, input().split())
	adj[a-1].append((b-1, -c+p))
	adj_rev[b-1].append(a-1)

s_reachable = [False for _ in range(n)]
s_reachable[0] = True
g_reachable = [False for _ in range(n)]
g_reachable[n-1] = True

def dfs_s(x):
	for v, w in adj[x]:
		if not s_reachable[v]:
			s_reachable[v] = True
			dfs_s(v)
	return

def dfs_g(x):
	for v in adj_rev[x]:
		if not g_reachable[v]:
			g_reachable[v] = True
			dfs_s(v)
	return

dfs_s(0)
dfs_g(n-1)

bf = BellmanFord(adj, 0, n)
bf.solve()
d = bf.GetDistance(n-1)
if d < -10**20:
	print(-1)
else:
	print(max(-d, 0))

Submission status: Runtime Error

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
	
class BellmanFord():
	def __init__(self, adj, start, size):
		self.adj = adj
		self.start = start
		self.size = len(adj)
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0

	def solve(self):
		for _ in range(self.size-1):
			for x, y, w in self.adj:
				if self.dist[y] > self.dist[x] + w:
					self.dist[y] = self.dist[x] + w
		return

	#負閉路のせいでgoalへの距離が-infになるか
	def NegativeCycleToGoal(self, goal):
		res = self.dist[goal]
		for _ in range(self.size):
			for x, y, w in self.adj:
				if self.dist[y] > self.dist[x] + w:
					self.dist[y] = 10**30
		if self.dist[goal] > 10**20:
			return True
		return False

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

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

bf = BellmanFord(adj, 0, n)
bf.solve()
if bf.NegativeCycleToGoal(n-1):
	print(-1)
else:
	print(max(-bf.GetDistance(n-1), 0))

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M, P = map(int, input().split())
e = dd(list)
for _ in range(M):
  a, b, c = map(int, input().split())
  e[a].append((b, -c + P))
class BellmanFord:
  def __init__(self, n, e):
    self.n = n
    self.edges = []
    self.b = pow(10, 10)
    for k in e.keys():
      for t in e[k]:
        self.edges.append(k * pow(b, 2) + t[0] * b + t[1])
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    d[s] = 0
    b = self.b
    for i in range(self.n + 1):
      for x in self.edges:
        u = x // pow(b, 2)
        v = x // b - u * b
        c = x % b
        if d[u] != float("inf") and (d[u] + c < d[v]):
          d[v] = d[u] + c
    return d[t]
  def path_findloop(self, s, t):
    d = [float("inf")] * (self.n + 1)
    d[s] = 0
    first = 0
    b = self.b
    for i in range(1, self.n * 2 + 1):
      for x in self.edges:
        u = x // pow(b, 2)
        v = x // b - u * b
        c = x % b
        print(u, v, c)
        if u != float("inf") and (d[u] + c < d[v]):
          d[v] = d[u] + c
          if i > N: d[v] = -float("inf")
      if i == self.n:
        first = d[t] + 0
      elif i == self.n * 2:
        if first != d[t]:
          return "-loop"
    return d[t]
bf = BellmanFord(N, e)
res = bf.path_findloop(1, N)
print(res)
if res == "-loop": print(-1)
else: print(max(0, -res))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N,M,P = map(int,input().split())
edge = [[] for _ in range(M)]
for i in range(M):
    A,B,C = map(int,input().split())
    edge[i].append(A-1,B-1,-(C-P))

def Bellman_Ford(edges, start, N):
    inf = float("inf")
    # dist[i]: 頂点iまでの最短距離
    dist = [inf for i in range(N)]
    dist[start] = 0

    for i in range(N+N):
        for a,b,c in edges:
            if a != inf and dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                # startからgoalまでに負閉路がある場合
                if i >= N:
                    dist[b] = -float("inf")
        # 一回目のベルマンフォード法の結果
        if i == N-1:
            first_time = dist[-1]
    # (一回目,二回目)
    return (first_time, dist[-1])

first,second = Bellman_Ford(edge, 0, N)
if first != second:
    answer = -1
else:
    answer = max(0,-second)

print(answer)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000000)
N,M,P=map(int,input().split())
okto=[False]*(N)
okot=[False]*(N)
okto[0]=True
okot[-1]=True
ok=[0]*(N)

d=[float('inf')]*M

def dfs(v):
    if okto[v]:
        return
    okto[v]=True
    for u in to[v]:
        dfs(u)
def rdfs(v):
    if okot[v]:
        return
    okot[v]=True
    for u in ot[v]:
        rdfs(u)
E=[0]*M
to=[[] for _ in range(N)]
ot=[[] for _ in range(N)]
for i in range(M):
    A,B,C = map(int, input().split())
    A=-A
    B=-B
    C=-C+P
    E[i]=[A,B,C]
    to[A].append(B)
    ot[B].append(A)
dfs(N-1)
rdfs(0)
for i in range(N):
    ok[i]=okto[i] and okot[i]
d[-1]=0
upd=True
step=0
while upd:
    upd=False
    for i in range(M):
        A,B,C=E[i]
        #print(E[i])
        if not ok[A]:
            continue
        if not ok[B]:
            continue
        newD=d[A]+C

        #print(newD)
        if newD<d[B]:
            upd=True
            d[B]=newD
    step+=1
    if step>N:
        print(-1)
        exit()

print(max(-d[0],0))

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000000)
N,M,P=map(int,input().split())
okto=[False]*(N)
okot=[False]*(N)

ok=[0]*(N)

d=[float('inf')]*M

def dfs(v):
    if okto[v]:
        return
    okto[v]=True
    for u in to[v]:
        dfs(u)
def rdfs(v):
    if okot[v]:
        return
    okot[v]=True
    for u in ot[v]:
        rdfs(u)
E=[0]*M
to=[[] for _ in range(N)]
ot=[[] for _ in range(N)]
for i in range(M):
    A,B,C = map(int, input().split())
    A=-A
    B=-B
    C=-C+P
    E[i]=[A,B,C]
    to[A].append(B)
    ot[B].append(A)
dfs(N-1)
rdfs(0)
for i in range(N):
    ok[i]=okto[i] and okot[i]
d[-1]=0
upd=True
step=0
while upd:
    upd=False
    for i in range(M):
        A,B,C=E[i]
        #print(E[i])
        if not ok[A]:
            continue
        if not ok[B]:
            continue
        newD=d[A]+C

        #print(newD)
        if newD<d[B]:
            upd=True
            d[B]=newD
    step+=1
    if step>N:
        print(-1)
        exit()

print(max(-d[0],0))

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000000000000)
N,M,P=map(int,input().split())
okto=[False]*(N)
okot=[False]*(N)

ok=[0]*(N)

d=[float('inf')]*M

def dfs(v):
    if okto[v]:
        return
    okto[v]=True
    for u in to[v]:
        dfs(u)
def rdfs(v):
    if okot[v]:
        return
    okot[v]=True
    for u in ot[v]:
        rdfs(u)
E=[0]*M
to=[[] for _ in range(N)]
ot=[[] for _ in range(N)]
for i in range(M):
    A,B,C = map(int, input().split())
    A=-A
    B=-B
    C=-C+P
    E[i]=[A,B,C]
    to[A].append(B)
    ot[B].append(A)
dfs(N-1)
rdfs(0)
for i in range(N):
    ok[i]=okto[i] and okot[i]
d[-1]=0
upd=True
step=0
while upd:
    upd=False
    for i in range(M):
        A,B,C=E[i]
        #print(E[i])
        if not ok[A]:
            continue
        if not ok[B]:
            continue
        newD=d[A]+C

        #print(newD)
        if newD<d[B]:
            upd=True
            d[B]=newD
    step+=1
    if step>N:
        print(-1)
        exit()

print(max(-d[0],0))

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(1000000000)
N,M,P=map(int,input().split())
okto=[False]*(N)
okot=[False]*(N)

ok=[0]*(N)

d=[float('inf')]*M

def dfs(v):
    if okto[v]:
        return
    okto[v]=True
    for u in to[v]:
        dfs(u)
def rdfs(v):
    if okot[v]:
        return
    okot[v]=True
    for u in ot[v]:
        rdfs(u)
E=[0]*M
to=[[] for _ in range(N)]
ot=[[] for _ in range(N)]
for i in range(M):
    A,B,C = map(int, input().split())
    A=-A
    B=-B
    C=-C+P
    E[i]=[A,B,C]
    to[A].append(B)
    ot[B].append(A)
dfs(N-1)
rdfs(0)
for i in range(N):
    ok[i]=okto[i] and okot[i]
d[-1]=0
upd=True
step=0
while upd:
    upd=False
    for i in range(M):
        A,B,C=E[i]
        #print(E[i])
        if not ok[A]:
            continue
        if not ok[B]:
            continue
        newD=d[A]+C

        #print(newD)
        if newD<d[B]:
            upd=True
            d[B]=newD
    step+=1
    if step>N:
        print(-1)
        exit()

print(max(-d[0],0))

Submission status: Runtime Error

Solution code:
N,M,P = map(int, input().split())

es = []

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

INF = float("inf")

d = [INF for _ in range(N)] 
d[0] = 0
"""
頂点Nに向かうまでに関係ない閉路に注意する

無限にコインを拾える場合、
・ある閉路を一周したときの得点と支払いの収支がプラス
・その閉路からゴールまで行ける
である。これがない場合、全てのノードを経由してゴールまで行く（N-1回移動）までにコインの枚数が最大になる
なので、一回ベルマンフォード法をやった後もう一回行って一回目と２回目でゴールまでのコイン枚数に変化があればゴ、
ールに行くまでの道に無限にコインをとれる閉路があるといえる

"""

def solve(start):
    for i in range(N):
        for a,b,c, in es:
            if d[a] != INF and d[a] + (-c) + P < d[b]:
                d[b] = d[a] + (-c) + P
                

                if i == N-1 and b == N-1:
                    return -1


    return max(-d[-1][0])


first=solve(0)
if first == -1:
    print(-1)
else:
    second=solve(0)
    if first == second:
        print(max(first, 0))
    else:
        print(-1)

Submission status: Runtime Error

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

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


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

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

    exist_negative_cycle = is_updated[goal]

    return dist, exist_negative_cycle

N, M, P = map(int,input().split())
edges = []
for _ in range(M):
    A, B, C = map(int,input().split())
    A -= 1; B -= 1
    C = C - P
    edges.append((A, B, -C))
 
dist, exist_negative_cycle = bellmanford(N, edges, 0, N-1)
 
if exist_negative_cycle is True:
    ans = -1
else:
    ans = max(-dist[N-1], 0)
 
print(ans)
inf = float('inf')
# ベルマンフォード法
# 計算量O(VE) V:頂点数, E:辺の数
# [引数]   n:頂点数, edges:辺集合, start:始点, end:終点
# [返り値] dist:startからの最短距離, exists_negative_cycle: 負閉路が存在するかどうか
def bellmanford(n : int, edges : list, start : int, goal : int) -> (list, bool):
    dist = [inf] * n
    dist[start] = 0
    exist_negative_cycle = True

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


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

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

    exist_negative_cycle = is_updated[goal]

    return dist, exist_negative_cycle

N, M, P = map(int,input().split())
edges = []
for _ in range(M):
    A, B, C = map(int,input().split())
    A -= 1; B -= 1
    C = C - P
    edges.append((A, B, -C))

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

if exist_negative_cycle is True:
    ans = -1
else:
    ans = max(-dist[N-1], 0)

print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!


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

el = []
for _ in range(m):
    a,b,c = map(int,input().split())
    el.append((a-1,b-1,c-p))
cost = [-float("inf") for _ in range(n)]
cost[0] = 0
for i in range(n+1):
    for j in range(m):
        e = el[j]
        if cost[e[1]] < cost[e[0]] + e[2]:
            cost[e[1]] = cost[e[0]] + e[2]
            if i == n:
                cost[e[1]] = float("inf")
              
if ans != cost[-1]:
    print(-1)
else:
    print(max(cost[-1], 0))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
from scipy.sparse import dok_matrix
from math import ceil

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

adj = [list() for _ in range(N)]
inv = [list() for _ in range(N)]
edges = []

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

stack = [N-1]
reachable1 = {N-1}
while stack:
    v = stack.pop()
    for u in inv[v]:
        if u not in reachable1:
            stack.append(u)
            reachable1.add(u)

stack = [0]
reachable2 = {0}
while stack:
    v = stack.pop()
    for u in adj[v]:
        if u not in reachable2:
            stack.append(u)
            reachable2.add(u)

reachable = reachable1 & reachable2
edges = [(a,b,w) for a,b,w in edges if a in reachable and b in reachable]

dist = [float('inf')]*N
dist[0] = 0

for i in range(len(reachable)-1):
    for a,b,w in edges:
        dist[b] = min(dist[a]+w, dist[b])

# negative cycle
for a,b,w in edges:
    if dist[b] > dist[a] + w:
        print(-1)
        break
else:
    print(max(0,-dist[-1]))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError
from scipy.sparse import dok_matrix

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

adj = [list() for _ in range(N)]
reachable = {N-1}


for _ in range(M):
    a,b,c = map(int,input().split())
    adj[b-1].append((a-1,c))
stack = [N-1]
while stack:
    v = stack.pop()
    for u,_ in adj[v]:
        if u not in reachable:
            stack.append(u)
            reachable.add(u)

G = dok_matrix((N,N))
for u,l in enumerate(adj):
    if u not in reachable:
        continue
    for v,c in l:
        if v not in reachable:
            continue
        w = -c+P
        w = 0.00000001 if w == 0 else w
        G[v,u] = w
try:
    D = bellman_ford(G, indices=0)
    print(max(0, int(-D[-1])))
except NegativeCycleError:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.readline


def main():
    total_node_num, edge_num, payment = [
        int(x) for x in input().strip().split()]
    edge_list = []
    for _ in range(edge_num):
        startNode, arriveNode, coin = [int(x) for x in input().strip().split()]
        edge_list.append([startNode-1, arriveNode-1, coin-payment])

    # ベルマンフォード法によりコインの最大値を求める
    # 1Tにpayment枚コインを払う必要があるということは実質のコストはcoin-payment
    node_point_list = [-np.inf for _ in range(total_node_num)]
    node_point_list[0] = 0
    ans = 0
    for loop_num in range(total_node_num):
        update_count = 0
        for edge_idx in range(edge_num):
            start_node = edge_list[edge_idx][0]
            arraive_node = edge_list[edge_idx][1]
            point = edge_list[edge_idx][2]
            if node_point_list[start_node]+point > node_point_list[arraive_node]:
                node_point_list[arraive_node] = node_point_list[start_node]+point
                update_count += 1
        if update_count == 0:
            break
        if loop_num == total_node_num - 2:
            ans = node_point_list[-1]
        if loop_num == total_node_num - 1 and ans != node_point_list[-1]:
            print(-1)
            return
    print(max(node_point_list[-1], 0))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
q=deque()
q.append(N)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in rev_al[fro]:
		if Visit[to]==0:
			q.append(to)
			
Visit1=Visit

#スタートからBFS
q=deque()
q.append(1)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in al[fro]:
		if Visit[to]==0:
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))


D=[ float("-inf") for _ in range(N+1) ]	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
for i in range(new_N):
	for a,b,c in fedge:
		if D[a]==float("-inf"): continue
		alt=D[a]+c
		if D[b]<alt:
			D[b]=alt
			if i==new_N-1:
				print -1
				quit()

print (max(0,D[N]))

Submission status: Runtime Error

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

def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source-1]=0
  
    #辺の緩和
    buf=0
    for i in range(num_v*2):
        for edge in edges:
            if dist[edge[0]] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i>=num_v:
                    dist[edge[1]-1] =-inf
        if i==num_v-2:
            buf=dist[-1]
    if dist[-1]!=buf or dist[-1]==inf:
        return False
    return dist[-1]*-1

x=BellmanFord(A,n,1)
if x==False:
    print(-1) 
else:
    print(x if x>0 else 0)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！

def BELLMANFORD(point,n,d,p):
    cost       = [-float("inf")]*(n+1)  #infじゃないと閉路検出がうまくいかない
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for nownode,nextnode,c in d:
            if cost[nextnode]<cost[nownode]+c-p:
                cost[nextnode]=cost[nownode]+c-p

    negative=[0]*(n+1)                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for nownode,nextnode,c in d:
            if negative[nownode]==1:
                negative[nextnode]=1
            if cost[nextnode]<cost[nownode]+c-p:
                cost[nextnode]=cost[nownode]+c-p
                negative[now]=1
 
    return cost,negative

def main():    
    n,m,p=map(int,input().split())

    d=[tuple(map(int,input().split()))for i in [0]*m]
    
    x,y=(BELLMANFORD(1,n,d,p))
    
    if y[n]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()