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.

Solution (Python):


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) ]	

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))




Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(N)
Visit[N]=1
while q:
	fro=q.popleft()
	for to in rev_al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)
			
Visit1=Visit



Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(1)
Visit[1]=1
while q:
	fro=q.popleft()
	for to in al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)

Visit2=Visit


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") ]*(N+1)	
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])

Solution (Python):

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) ]	

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))




Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(N)
Visit[N]=1
while q:
	fro=q.popleft()
	for to in rev_al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)
			
Visit1=Visit



Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(1)
Visit[1]=1
while q:
	fro=q.popleft()
	for to in al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)

Visit2=Visit


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") ]*(N+1)	
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])

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)

ii = lambda: int(input())
miis = lambda: map(int, input().split())
lmiis = lambda: list(miis())

def reachable_nodeset(start, inc):
    reachable = set()
    reachable.add(start)
    nodes = [start]

    while nodes:
        n = nodes.pop()
        for i in inc[n]:
            if i not in reachable:
                nodes.append(i)
                reachable.add(i)

    return reachable

def bellmanford(num, start, goal, edges):
    cost = [float('inf')] * num
    cost[start] = 0

    for _ in range(num):
        updated = False
        for a, b, c in edges:
            if cost[b] > cost[a] + c:
                cost[b] = cost[a] + c
                updated = True
        if not updated: break
    else:
        return -1

    return max(0, -cost[goal])

def solve():
    N, M, P = miis()
    to = [[] for _ in range(N)]
    ot = [[] for _ in range(N)]
    edges = []

    for _ in range(M):
        a, b, c = miis()
        a -= 1
        b -= 1
        c = -(c - P)

        to[a].append(b)
        ot[b].append(a)
        edges.append((a,b,c))

    reachableFromZero = reachable_nodeset(0, to)
    reachableToN = reachable_nodeset(N-1, ot)
    ok = reachableFromZero.intersection(reachableToN)

    edges = tuple((a,b,c) for a, b, c in edges if a in ok and b in ok)

    print(bellmanford(N, 0, N-1, edges))

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,M,P = map(int,readline().split())
ABC = np.array(read().split(),np.int64)

A = ABC[::3]
B = ABC[1::3]
C = ABC[2::3]

C = P-C



INF = 10**18
dist = np.full(N+1,INF,np.int64)
dist[1] = 0
for T in range(N+N+10):
    x = dist[A] + C
    update = (dist[B] > x) & (x < INF//2)
    b = B[update]; x = x[update]
    if T > N:
        dist[b] = -INF
    else:
        ind = x.argsort(); x = x[ind][::-1]; b=b[ind][::-1]
        dist[b] = x

answer = -dist[N]
if answer < 0:
    answer = 0
elif answer == INF:
    answer = -1
print(answer)

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

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[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-1:
            buf=dist[-1]
    if dist[-1]!=buf or dist[-1]==-inf:
        return -1
    return max(dist[-1],0)

x=BellmanFord(A,n,1)
print(x)

Solution (Python):
"""解説を見てから解いたコード"""
N, M, P = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a, b, c-P))

INF = float('inf')

coin_map = [-INF] * (N+1)
coin_map[1] = 0

for i in range(2*N):
    for a, b, c in edges:
        if coin_map[b] < coin_map[a] + c:
            coin_map[b] = coin_map[a] + c
            if i >= N:
                coin_map[b] = INF

    if i == N - 1:
        ans = coin_map[N]

if ans != coin_map[N]:
    print(-1)
else:
    print(max(0, coin_map[N]))

Solution (Python):
import sys
input=sys.stdin.readline  

def BELLMANFORD(point,n,d,p):
    cost       = [1e18]*(n+1)  
    cost[point]= 0
    for i in range(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)                                        
    
    for i in range(n):                  
        for nownode,nextnode,c in d:
            if negative[nownode]:
                negative[nextnode]=1
            if cost[nextnode]>cost[nownode]+c+p and cost[nextnode]<1e17 and cost[nownode]+c+p<1e17:
                cost[nextnode]=cost[nownode]+c+p
                
                negative[nownode]=1
    
    
    return cost,negative

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

    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline  

def BELLMANFORD(point,n,d,p):
    cost       = [-float("inf")]*(n+1)  
    cost[point]= 0
    for i in range(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)                                        
    
    for i in range(n):                  
        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[nownode]=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()

Solution (Python):
import sys
input=sys.stdin.readline  

def BELLMANFORD(point,n,d,p):
    cost       = [-float("inf")]*(n+1)  
    cost[point]= 0
    for i in range(n-1):                                  
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*(n+1)                                        
    
    for i in range(n):                  
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now]==1:
                    negative[nex]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now]=1
 
    return cost,negative

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

    d={}
    for s in range(m):
        a,b,c=map(int,input().split())
        if a in d:
            d[a].append((b,c))
        else:
            d[a]=[(b,c)]
    
    x,y=(BELLMANFORD(1,n,d,p))
    
    if y[n]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()

Solution (Python):


import sys
input=sys.stdin.readline  

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

d={}
for s in range(m):
    a,b,c=map(int,input().split())
    if a in d:
        d[a].append((b,c))
    else:
        d[a]=[(b,c)]




def BELLMANFORD(point,d,p):
    cost       = [-float("inf")]*(n+1)  
    cost[point]= 0
    for i in range(n-1):                                  
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*(n+1)                                        
    
    for i in range(n):                  
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now]==1:
                    negative[nex]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
    
    if y[n]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()

Solution (Python):

import sys
input=sys.stdin.readline  

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

d={}
for s in range(m):
    a,b,c=map(int,input().split())
    if a in d:
        d[a].append((b,c))
    else:
        d[a]=[(b,c)]




def BELLMANFORD(point,d,p):
    cost       = [-float("inf")]*(n+1)  
    cost[point]= 0
    for i in range(n-1):                                  
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*n                                        
    
    for i in range(n):                  
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now-1]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
    
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline  


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

d={}
for s in range(m):
    a,b,c=map(int,input().split())
    if a in d:
        d[a].append((b,c))
    else:
        d[a]=[(b,c)]




def BELLMANFORD(point,d,p):
    cost       = [-float("inf") for node in range(n+1)]  
    cost[point]= 0
    for i in range(n-1):                                  
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*n                                        
    
    for i in range(n):                  
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now-1]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
    
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()

Solution (Python):
"""解説を見てから解いたコード"""
N, M, P = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a, b, c-P))

INF = float('inf')

coin_map = [-INF] * (N+1)
coin_map[1] = 0

for i in range(2*N):
    for a, b, c in edges:
        if coin_map[b] < coin_map[a] + c:
            coin_map[b] = coin_map[a] + c
            if i >= N:
                coin_map[b] = INF

    if i == N - 1:
        ans = coin_map[N]

if ans != coin_map[N]:
    print(-1)
else:
    print(max(0, coin_map[N]))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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

edges = []
routes  = [[] for i in range(n)]
rev_routes = [[] for i in range(n)]
from_start = set()
to_goal = set()

def dfs(node, routes, seen):
    if node in seen:
        return
    seen.add(node)
    candidates = routes[node]
    for to in candidates:
        dfs(to, routes, seen)


for _ in range(m):
    node1, node2, value = map(int, input().split())
    node1, node2, value = node1-1, node2-1, value - p
    edges.append([node1, node2, value])
    routes[node1].append(node2)
    rev_routes[node2].append(node1)

dfs(0, routes, from_start)
dfs(n-1, rev_routes, to_goal)

from_start_to_goal = from_start & to_goal

graph = [-float('INF')] * n
graph[0] = 0

for i in range(n):
    is_updated = False
    for node, to, value in edges:
        if node not in from_start_to_goal or to not in from_start_to_goal:
            continue
        current_point = graph[node]
        next_point = graph[node] + value
        if graph[to] < next_point:
            graph[to] = next_point
            is_updated = True
        else:
            continue
    if not is_updated:
        score = max(0, graph[n-1])
        break
else:
    score = -1
      
print(score)

Solution (Python):
import time

t1 = time.time()

N, M, P = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]

to_w = [set() for _ in range(N)]
for a, b, c in ABC:
    to_w[a - 1].add((b - 1, P - c))
reachable_from_start = {0}
q = {0}
while q:
    u = q.pop()
    for v, _ in to_w[u]:
        if v not in reachable_from_start:
            reachable_from_start.add(v)
            q.add(v)


from_w = [set() for _ in range(N)]
for a, b, c in ABC:
    from_w[b - 1].add((a - 1, P - c))
reachable_to_goal = {N - 1}
q = {N - 1}
while q:
    u = q.pop()
    for v, _ in from_w[u]:
        if v not in reachable_to_goal:
            reachable_to_goal.add(v)
            q.add(v)


reachable = reachable_from_start & reachable_to_goal


to_w = [set() for _ in range(N)]
for a, b, c in ABC:
    if a - 1 in reachable and b - 1 in reachable:
        to_w[a - 1].add((b - 1, P - c))
d = [float("inf")] * N
d[0] = 0
q = {0}
while q:
    u = q.pop()

    for v, w in to_w[u]:
        tmp = d[u] + w
        if tmp < d[v]:
            d[v] = tmp
            if v not in q:
                q.add(v)

        if time.time() > 1.9 + t1:
            d[-1] = -float("inf")
            break
    else:
        continue
    break

if d[-1] == -float("inf"):
    print(-1)
else:
    print(max(0, -d[-1]))

Solution (Python):
def reachable(es, source):
	ret = {source}
	Q = [source]
	while Q:
		cur = Q.pop()
		for nxt in es[cur]:
			if nxt not in ret:
				Q.append(nxt)
				ret.add(nxt)
	return ret

def BellmanFord(V:int, es:list, source=0):
	INF = float("inf")
	D = [INF]*V
	D[source] = 0
	for _ in range(V):
		upd = False
		for f, t, c in es:
			tmp = D[f] + c
			if D[t] > tmp:
				D[t] = tmp
				upd = True
		if not upd:
			return D[-1]
	else:
		return None
	
def main():
	N,M,P,*L=map(int,open(0).read().split())
	fwd = [[] for _ in range(N)]
	bwd = [[] for _ in range(N)]
	tmp = []
	for a,b,c in zip(*[iter(L)]*3):
		fwd[a-1].append(b-1)
		bwd[b-1].append(a-1)
		tmp+=[(a-1,b-1,P-c)]
	judge = reachable(fwd,0) & reachable(bwd,N-1)
	ans = BellmanFord(N,[(a,b,c) for a,b,c in tmp if a in judge and b in judge])
	if ans==None:
		print(-1)
	else:
		print(max(0,-ans))

if __name__=="__main__":
	main()

Solution (Python):
def reachable(es, source):
	ret = {source}
	Q = [source]
	while Q:
		cur = Q.pop()
		for nxt in es[cur]:
			if nxt not in ret:
				Q.append(nxt)
				ret.add(nxt)
	return ret

def BellmanFord(V:int, es:list, source=0):
	INF = float("inf")
	D = [INF]*V
	D[source] = 0
	for _ in range(V):
		upd = False
		for f, t, c in es:
			tmp = D[f] + c
			if D[t] > tmp:
				D[t] = tmp
				upd = True
		if not upd:
			return D[-1]
	else:
		return None
	
def main():
	N,M,P,*L=map(int,open(0).read().split())
	fwd = [[] for _ in range(N)]
	bwd = [[] for _ in range(N)]
	for a,b in zip(L[::3],L[1::3]):
		fwd[a-1].append(b-1)
		bwd[b-1].append(a-1)
	judge = reachable(fwd,0) & reachable(bwd,N-1)
	G = [(a-1,b-1,P-c) for a,b,c in zip(*[iter(L)]*3) if a-1 in judge and b-1 in judge]
	ans = BellmanFord(N,G)
	if ans==None:
		print(-1)
	else:
		print(max(0,-ans))

if __name__=="__main__":
	main()

Solution (Python):
from collections import deque

def reachable(es, source):
	ret = {source}
	Q = [source]
	while Q:
		cur = Q.pop()
		for nxt in es[cur]:
			if nxt not in ret:
				Q.append(nxt)
				ret.add(nxt)
	return ret

def SPFA(G:list, source=0):
	V = len(G)
	d = [float("inf")]*V
	inQ = [False]*V
	cnt = [0]*V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	while Q:
		f = Q.popleft()
		inQ[f] = False
		for t,c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					Q.append(t)
					inQ[t] = True
					cnt[t] += 1
					front = Q.popleft()
					if d[front] > dist:
						Q.append(front)
					else:
						Q.appendleft(front)
				if cnt[t] > V:
					
					return None
	return d[-1]
	
def main():
	N,M,P,*L=map(int,open(0).read().split())
	fwd = [[] for _ in range(N)]
	bwd = [[] for _ in range(N)]
	G = [[] for _ in range(N)]
	for a,b in zip(L[::3],L[1::3]):
		fwd[a-1].append(b-1)
		bwd[b-1].append(a-1)
	judge = reachable(fwd,0) & reachable(bwd,N-1)
	for a,b,c in zip(*[iter(L)]*3):
		if a-1 in judge and b-1 in judge:
			G[a-1].append((b-1,P-c))
	ans = SPFA(G)
	if ans==None:
		print(-1)
	else:
		print(max(0,-ans))

if __name__=="__main__":
	main()

Solution (Python):
from collections import deque

def reachable(es, source):
	ret = {source}
	Q = [source]
	while Q:
		cur = Q.pop()
		for nxt in es[cur]:
			if nxt not in ret:
				Q.append(nxt)
				ret.add(nxt)
	return ret

def SPFA(G:list, source=0):
	from collections import deque
	V = len(G)
	d = [float("inf")]*V
	inQ = [False]*V
	cnt = [0]*V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	_sum = 0
	_len = 1
	while Q:
		f = Q.popleft()
		inQ[f] = False
		_sum -= d[f]
		_len -= 1
		for t,c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					inQ[t] = True
					cnt[t] += 1
					if dist*_len < _sum:
						Q.appendleft(t)
					else:
						Q.append(t)
					_sum += dist
					_len += 1
				if cnt[t] > V:
					
					return None
	return d[-1]
	
def main():
	N,M,P,*L=map(int,open(0).read().split())
	fwd = [[] for _ in range(N)]
	bwd = [[] for _ in range(N)]
	G = [[] for _ in range(N)]
	for a,b in zip(L[::3],L[1::3]):
		fwd[a-1].append(b-1)
		bwd[b-1].append(a-1)
	judge = reachable(fwd,0) & reachable(bwd,N-1)
	for a,b,c in zip(*[iter(L)]*3):
		if a-1 in judge and b-1 in judge:
			G[a-1].append((b-1,P-c))
	ans = SPFA(G)
	if ans==None:
		print(-1)
	else:
		print(max(0,-ans))

if __name__=="__main__":
	main()

Solution (Python):
from collections import deque

def reachable(es, source):
	ret = {source}
	Q = deque([source])
	while Q:
		cur = Q.popleft()
		for nxt in es[cur]:
			if nxt not in ret:
				Q.append(nxt)
				ret.add(nxt)
	return ret

def SPFA(G:list, source=0):
	from collections import deque
	V = len(G)
	d = [float("inf")]*V
	inQ = [False]*V
	cnt = [0]*V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	_sum = 0
	_len = 1
	while Q:
		f = Q.popleft()
		inQ[f] = False
		_sum -= d[f]
		_len -= 1
		for t,c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					inQ[t] = True
					cnt[t] += 1
					if dist*_len < _sum:
						Q.appendleft(t)
					else:
						Q.append(t)
					_sum += dist
					_len += 1
				if cnt[t] > V:
					
					return None
	return d[-1]
	
def main():
	N,M,P,*L=map(int,open(0).read().split())
	fwd = [[] for _ in range(N)]
	bwd = [[] for _ in range(N)]
	G = [[] for _ in range(N)]
	for a,b in zip(L[::3],L[1::3]):
		fwd[a-1].append(b-1)
		bwd[b-1].append(a-1)
	judge = reachable(fwd,0) & reachable(bwd,N-1)
	for a,b,c in zip(*[iter(L)]*3):
		if a-1 in judge and b-1 in judge:
			G[a-1].append((b-1,P-c))
	ans = SPFA(G)
	if ans==None:
		print(-1)
	else:
		print(max(0,-ans))

if __name__=="__main__":
	main()

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

d = [float('inf')] * n
d[0] = 0

for i in range(n):
    for a, b, c in abc:
        d[b] = min(d[b], d[a] + c)

for a, b, c in abc:
    if d[b] > d[a] + c:
        d[b] = - float('inf')

for i in range(n):
    for a, b, c in abc:
        d[b] = min(d[b], d[a] + c)

if d[n-1] == - float('inf'):
    print(-1)
else:
    print(max(0, - d[n-1]))

Solution (Python):
def main():
    INF = float("inf")

    N, M, P, *ABC = map(int, open(0).read().split())

    F = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    E = [(a - 1, b - 1, P - c) for a, b, c in zip(*[iter(ABC)] * 3)]

    for a, b, c in E:
        F[a].append(b)
        B[b].append(a)

    def reachable(E, a):
        S = {a}
        stack = [a]
        while stack:
            s = stack.pop()
            for v in E[s]:
                if v not in S:
                    stack.append(v)
                    S.add(v)
        return S

    ok = reachable(F, 0) & reachable(B, N - 1)

    E = [(a, b, c) for a, b, c in E if a in ok and b in ok]

    D = [INF] * N
    D[0] = 0

    def bellman_ford(N):
        for _ in range(N):
            update = False
            for a, b, c in E:
                if D[b] > D[a] + c:
                    D[b] = D[a] + c
                    update = True
            if not update:
                return False
        return True

    print(-1 if bellman_ford(N + 1) else max(-D[-1], 0))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    INF = float("inf")

    N, M, P, *ABC = map(int, open(0).read().split())

    F = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    E = [(a - 1, b - 1, P - c) for a, b, c in zip(*[iter(ABC)] * 3)]

    for a, b, c in E:
        F[a].append(b)
        B[b].append(a)

    S = {0}
    stack = [0]
    while stack:
        s = stack.pop()
        for v in F[s]:
            if v not in S:
                stack.append(v)
                S.add(v)

    T = {N - 1}
    stack = [N - 1]
    while stack:
        s = stack.pop()
        for v in B[s]:
            if v not in T:
                stack.append(v)
                T.add(v)

    ok = S & T

    E = [(a, b, c) for a, b, c in E if a in ok and b in ok]

    D = [INF] * N
    D[0] = 0

    def bellman_ford(N):
        for _ in range(N):
            update = False
            for a, b, c in E:
                if D[b] > D[a] + c:
                    D[b] = D[a] + c
                    update = True
            if not update:
                return False
        return True

    print(-1 if bellman_ford(N + 1) else max(-D[-1], 0))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    INF = float("inf")

    N, M, P, *ABC = map(int, open(0).read().split())

    F = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    E = [(a - 1, b - 1, P - c) for a, b, c in zip(*[iter(ABC)] * 3)]

    for a, b, c in E:
        F[a].append(b)
        B[b].append(a)

    S = {0}
    stack = [0]
    while stack:
        s = stack.pop()
        for v in F[s]:
            if v not in S:
                stack.append(v)
                S.add(v)

    T = {N - 1}
    stack = [N - 1]
    while stack:
        s = stack.pop()
        for v in B[s]:
            if v not in T:
                stack.append(v)
                T.add(v)

    ok = S & T

    E = [(a, b, c) for a, b, c in E if a in ok and b in ok]

    D = [INF] * N
    D[0] = 0

    def bellman_ford(N):
        for _ in range(N):
            update = False
            for a, b, c in E:
                if D[b] > D[a] + c:
                    D[b] = D[a] + c
                    update = True
            if not update:
                return False
        return True

    bellman_ford(N)

    print(-1 if bellman_ford(1) else max(-D[-1], 0))



if __name__ == '__main__':
    main()

Solution (Python):
def main():
    INF = float("inf")

    N, M, P, *ABC = map(int, open(0).read().split())

    F = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    E = [(a - 1, b - 1, P - c) for a, b, c in zip(*[iter(ABC)] * 3)]

    for a, b, c in E:
        F[a].append(b)
        B[b].append(a)

    S = {0}
    stack = [0]
    while stack:
        s = stack.pop()
        for v in F[s]:
            if v not in S:
                stack.append(v)
                S.add(v)

    T = {N - 1}
    stack = [N - 1]
    while stack:
        s = stack.pop()
        for v in B[s]:
            if v not in T:
                stack.append(v)
                T.add(v)

    ok = S & T

    D = [INF] * N
    D[0] = 0

    def bellman_ford(N):
        for _ in range(N):
            update = False
            for a, b, c in E:
                if a in ok and b in ok and D[b] > D[a] + c:
                    D[b] = D[a] + c
                    update = True
            if not update:
                return False
        return True

    bellman_ford(N)

    print(-1 if bellman_ford(1) else max(-D[-1], 0))



if __name__ == '__main__':
    main()

Solution (Python):
n, m, p = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
 
for i in range(m):
    lst[i][2] = - (lst[i][2] - p)

d = [10**100] * (n+1)
d[1] = 0
rep = 0
 
while True:
    update = False
    for edge in lst:
        a,b,c = edge
        if d[a] != 10**100 and d[b] > d[a]+ c:
            if rep >= n:
                d[b] = -10**100
            else:
                d[b] = d[a] + c
            update = True
    if not update:
        break
    rep += 1
    if rep > 2*n:
        break

if d[n] <= - 10**100:
    print(-1)
elif -d[n] < 0:
    print(0)
else:
    print(-d[n])

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
INF = float('inf')

def bellmanford(edges, s, t, se):
    N = len(edges)
    dist = [INF] * N
    dist[s] = 0
    for i in range(N):
        update = False
        for v in range(N):
            if v not in se or dist[v] == INF:
                continue
            for u, c in edges[v]:
                if u not in se:
                    continue
                d = dist[v] + c
                if d < dist[u]:
                    dist[u] = d
                    update = True
        if update == False:
            return max(0, -dist[t])
    else:
        return -1

N, M, P = map(int, input().split())
es = [[] for i in range(N)]
es_r = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    es[a-1].append((b-1, P-c))
    es_r[b-1].append(a-1)
reachable1 = [False] * N
def dfs(v):
    if reachable1[v]: return
    reachable1[v] = True
    for u, c in es[v]:
        dfs(u)
reachable2 = [False] * N
def rdfs(v):
    if reachable2[v]: return
    reachable2[v] = True
    for u in es_r[v]:
        rdfs(u)
dfs(0)
rdfs(N-1)
se = set()
for i in range(N):
    if reachable1[i] and reachable2[i]:
        se.add(i)
print(bellmanford(es, 0, N-1, se))