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):
from collections import deque
import sys
input = sys.stdin.readline

INF = float('inf')

def BellmanFord(adjList, vSt, INF):
    numV = len(adjList)
    negINF = -INF
    costs = [INF] * numV
    costs[vSt] = 0
    vNows = set([vSt])

    for _ in range(numV):
        vChangeds = set()
        for vFr in vNows:
            costFr = costs[vFr]
            for vTo, wt in adjList[vFr]:
                c2 = costFr + wt
                if c2 < costs[vTo]:
                    costs[vTo] = c2
                    vChangeds.add(vTo)
        if not vChangeds:
            return costs
        vNows = vChangeds

    for v in vNows:
        costs[v] = negINF

    Q = deque(vNows)
    while Q:
        vFr = Q.popleft()
        for vTo, wt in adjList[vFr]:
            if costs[vTo] == negINF: continue
            costs[vTo] = negINF
            Q.append(vTo)

    return costs


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

costs = BellmanFord(adjL, 0, INF)

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

Solution (Python):

"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

import sys
sys.setrecursionlimit(200000)

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

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    inf = 10**17
    

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

    visited = [0]*n
    visited[-1] = 1
    dq = deque([n-1])
    while dq:
        v = dq.popleft()
        for nv in adj[v]:
            if visited[nv] == 0:
                visited[nv] = 1
                dq.append(nv)
    
    def bellmanford(n, s, edge):
        inf = 10**17
        d = [inf] * n
        d[s] = 0
        for i in range(n):
            for a,b,c in edge:
                if d[a] != inf and d[b] > d[a]+c:
                    d[b] = d[a] + c
                    if i == n-1 and visited[b] == 1:
                        return -inf
        return -d[-1]

    res = bellmanford(n,0,edge)
    if res == -inf:
        print(-1)
    elif res < 0:
        print(0)
    else:
        print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

INF = 10 ** 9
N, M, P = map(int,input().split())

edges = []

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

flag1 = [0] * N
flag2 = [0] * N
flag = [0] * N

flag1[0] = 1
flag2[N-1] = 1

for i in range(N-1):
    for j in range(M):
        edge = edges[j]
        if flag1[edge[0]]:
            flag1[edge[1]] = 1
        if flag2[edge[1]]:
            flag2[edge[0]] = 1

for i in range(N):
    if flag1[i] and flag2[i]:
        flag[i] = 1

d = [INF] * N
d[0] = 0
k = None

for i in range(N):
    for j in range(M):
        edge = edges[j]
        if d[edge[1]] > d[edge[0]] + edge[2]:
            d[edge[1]] = d[edge[0]] + edge[2]
            if i == N - 1 and flag[edge[1]]:
                print(-1)
                sys.exit()

print(max(-1 * d[N-1], 0))

Solution (Python):
from collections import deque
N,M,P,*L = map(int, open(0).read().split())
INF = 10**9
Els = []
dic = [[] for i in range(N+1)]
rdic = [[] for i in range(N+1)]
for a,b,c in zip(*[iter(L)]*3):
  dic[a].append((b,c-P))
  rdic[b].append((a,c-P))
  Els.append((a,b,-c+P))
ok1 = [False]*(N+1)
ok1[1] = True
q = deque([1])
while q:
  v = q.popleft()
  for p,c in dic[v]:
    if not ok1[p]:
      ok1[p] = True
      q.append(p)

ok2 = [False]*(N+1)
ok2[N] = True
q = deque([N])
while q:
  v = q.popleft()
  for p,c in rdic[v]:
    if not ok2[p]:
      ok2[p] = True
      q.append(p)

ok = [a&b for a,b in zip(ok1,ok2)]

dist = [INF]*(N+1)
dist[1] = 0
cnt = 0
while True:
  end = True
  for a,b,c in Els:
    if ok[a] and ok[b] and dist[a]!=INF and dist[b]>dist[a]+c:
      end = False
      dist[b] = dist[a]+c
  if end:
    print(max(0,-dist[N]))
    break
  cnt += 1
  if cnt>N:
    print(-1)
    break

Solution (Python):
from collections import deque
N,M,P,*L = map(int, open(0).read().split())
INF = 10**9
Els = []
dic = [[] for i in range(N+1)]
rdic = [[] for i in range(N+1)]
for a,b,c in zip(*[iter(L)]*3):
  dic[a].append((b,c-P))
  rdic[b].append((a,c-P))
  Els.append((a,b,-c+P))
ok1 = [False]*(N+1)
ok1[1] = True
q = deque([1])
while q:
  v = q.popleft()
  for p,c in dic[v]:
    if not ok1[p]:
      ok1[p] = True
      q.append(p)

ok2 = [False]*(N+1)
ok2[N] = True
q = deque([N])
while q:
  v = q.popleft()
  for p,c in rdic[v]:
    if not ok2[p]:
      ok2[p] = True
      q.append(p)

ok = [a&b for a,b in zip(ok1,ok2)]

dist = [INF]*(N+1)
dist[1] = 0
cnt = 0
while True:
  end = True
  for a,b,c in Els:
    if ok[a] and ok[b] and dist[a]!=INF and dist[b]>dist[a]+c:
      end = False
      dist[b] = dist[a]+c
  if end:
    print(max(0,-dist[N]))
    break
  cnt += 1
  if cnt>2*M:
    print(-1)
    break

Solution (Python):
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bellman_ford(edges, n_nodes, start, goal):
    dist = [float("inf") for _ in range(n_nodes)]
    dist[start] = 0

    for i in range(2 * n_nodes):
        for fro, to, cost in edges:
            if dist[to] > dist[fro] + cost:
                dist[to] = dist[fro] + cost
                if i == n_nodes - 1:
                    dist[to] = -float("inf")

    return -dist[goal]


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

    ans = bellman_ford(edges, N, 0, N - 1)
    if ans == float("inf"):
        print(-1)
    else:
        print(max(ans, 0))


if __name__ == "__main__":
    main()

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


def bellman_ford(edges, N, start):
    dist = [float("inf") for _ in range(N)]
    dist[start] = 0
    
    
    
    
    for i in range(2 * N):
        for fro, to, cost in edges:
            if dist[to] > dist[fro] - cost:
                dist[to] = dist[fro] - cost
                
                if i == N - 1:
                    dist[to] = -float("inf")

    return dist


def main():
    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, C - P))
    dist = bellman_ford(edge, N, 0)

    if dist[-1] == -float("inf"):
        print(-1)
    else:
        if dist[-1] > 0:
            print(0)
        else:
            print(-1 * dist[-1])


if __name__ == "__main__":
    main()

Solution (Python):
INF=10**30
def Belman_Ford(s,N,Edge):
    dist=[INF]*N
    neg=[False]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=min(dist[t],dist[f]+c)
    for i in range(N):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=dist[f]+c
                neg[t]=True
            if neg[f]:
                neg[t]=True
    return dist,neg
                
N,M,P=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    Edge.append((a-1,b-1,-(c-P)))
dist,neg=Belman_Ford(0,N,Edge)

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

Solution (Python):

import heapq
import sys
sys.setrecursionlimit(10**9)









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

Edge = [[] for _ in range(N)]
for a,b,c in ABC:
    Edge[b-1].append(a-1)


reachable = [False]*N
reachable[N-1] = True

def dfs(v):
    for nv in Edge[v]:
        if reachable[nv]:
            continue
        else:
            reachable[nv] = True
            dfs(nv)
    return 

def BellmanFord(s, N, Edge):
    INF = 10**20
    dist = [INF] * N
    dist[s] = 0
    for i in range(N):
        isUpdated = False
        for t in range(N):
            if dist[t] == INF:
                continue
            for v,c in Edge[t]:
                if dist[t]+c < dist[v]:
                    dist[v] = dist[t]+c
                    isUpdated = True
        if not isUpdated:
            break
        elif i==N-1:
            return -1
    return dist

                
dfs(N-1)
newEdge = [[] for _ in range(N)]
for a,b,c in ABC:
    if reachable[a-1]:
        newEdge[a-1].append([b-1, P-c])

dist = BellmanFord(0, N, newEdge)
if dist==-1:
    print(-1)
else:
    print(max(0, -dist[N-1]))

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M, P = (int(i) for i in input().split())
    adj_list = [[] for _ in range(N)]
    radj_list = [[] for _ in range(N)]
    ok = [False]*N
    edge = []
    for i in range(M):
        a, b, c = (int(i) for i in input().split())
        c -= P
        adj_list[a-1].append(b-1)
        radj_list[b-1].append(a-1)
        edge.append((a-1, b-1, -c))

    def dfs(G, v):
        seen = [False]*N
        todo = [v]
        seen[v] = True
        while todo:
            u = todo.pop()
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                seen[next_v] = True
                todo.append(next_v)
        return seen

    i = 0
    for s, rs in zip(dfs(adj_list, 0), dfs(radj_list, N-1)):
        ok[i] = s and rs
        i += 1

    
    d = [10**12]*N
    d[0] = 0
    update = True
    step = 0
    while update:
        update = False
        for a, b, c in edge:
            if not(ok[a]) or not(ok[b]):
                continue
            newD = d[a] + c
            if newD < d[b]:
                update = True
                d[b] = newD
        step += 1
        if step > N:
            return print(-1)
    print(max(0, d[N-1]*-1))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from itertools import product
    import sys
    input = sys.stdin.buffer.readline
    N, M, P = (int(i) for i in input().split())
    adj_list = [[] for _ in range(N)]
    radj_list = [[] for _ in range(N)]
    ok = [False]*N
    edge = []
    for i in range(M):
        a, b, c = (int(i) for i in input().split())
        c -= P
        adj_list[a-1].append(b-1)
        radj_list[b-1].append(a-1)
        edge.append((a-1, b-1, -c))

    def dfs(G, v):
        seen = [False]*N
        todo = [v]
        seen[v] = True
        while todo:
            u = todo.pop()
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                seen[next_v] = True
                todo.append(next_v)
        return seen

    i = 0
    for s, rs in zip(dfs(adj_list, 0), dfs(radj_list, N-1)):
        ok[i] = s and rs
        i += 1

    
    d = [10**12]*N
    d[0] = 0
    update = True
    step = 0
    while update:
        update = False
        for a, b, c in edge:
            if not(ok[a]) or not(ok[b]):
                continue
            newD = d[a] + c
            if newD < d[b]:
                update = True
                d[b] = newD
        step += 1
        if step > N:
            return print(-1)
    print(max(0, d[N-1]*-1))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N,M,P=map(int, input().split())
    E=[]
    G=[[] for _ in range(N)]
    H=[[] for _ in range(N)]
    for _ in range(M):
        a,b,c=map(int, input().split())
        a,b=a-1,b-1
        E.append((a,b,c-P))
        G[b].append(a)
        H[a].append(b)

    R1=[False]*N
    R1[0]=True
    stk=[0]
    while stk:
        v=stk.pop()
        for to in H[v]:
            if R1[to]: continue
            R1[to]=True
            stk.append(to)

    R2=[False]*N
    R2[N-1]=True
    stk=[N-1]
    while stk:
        v=stk.pop()
        for to in G[v]:
            if R2[to]: continue
            R2[to]=True
            stk.append(to)

    INF=10**10
    d=[-INF]*N
    d[0]=0
    for i in range(N):
        for a,b,c in E:
            if R1[a]==False: continue
            if R2[b]==False: continue
            if d[a]==-INF: continue
            if d[b] < d[a] + c:
                d[b] = d[a] + c
                if i==N-1:
                    print(-1)
                    return
    print(max(0,d[N-1]))

if __name__ == '__main__':
    main()

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

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

    INF = 10 ** 9
    

    
    
    G = []
    for _ in range(M): 
        A, B, C = map(int, input().split()) 
        G += [[A - 1, B - 1, P - C]] 

    check = [False] * N
    d = [INF] * N 

    def shortest_path(s): 
        s -= 1
        d[s] = 0
        j = 0
        while j < N - 1:
            for i in range(M): 
                e = G[i]
                if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
            j += 1
        
        j = 0
        while j < N:
            for i in range(M):
                e = G[i]
                if d[e[0]] == INF:
                    continue
                if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    check[e[1]] = True
                if check[e[0]]:
                    check[e[1]] = True
            j += 1

    shortest_path(1)
    if check[N - 1]:
        print (-1)
    else:
        ans = d[N - 1]
        print (max(0, -ans))
    

if __name__ == '__main__':
    main()

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

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

INF = 10 ** 9




G = []
for _ in range(M): 
    A, B, C = map(int, input().split()) 
    G += [[A - 1, B - 1, P - C]] 

check = [False] * N
d = [INF] * N 

def shortest_path(s): 
    s -= 1
    d[s] = 0
    j = 0
    while j < N - 1:
        for i in range(M): 
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
        j += 1
    
    j = 0
    while j < N:
        for i in range(M):
            e = G[i]
            if d[e[0]] == INF:
                continue
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                check[e[1]] = True
            if check[e[0]]:
                check[e[1]] = True
        j += 1

shortest_path(1)
if check[N - 1]:
    print (-1)
else:
    ans = d[N - 1]
    print (max(0, -ans))

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

edges = [[] for _ in range(N)]
edgesR = [[] for _ in range(N)]
E = []
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    E.append((fr, to, -(c - P)))
    edges[fr].append(to)
    edgesR[to].append(fr)

def dfs(edges, s):
    visited = [False] * N
    st = [s]
    visited[s] = True
    while st:
        for to in edges[st.pop()]:
            if not visited[to]:
                st.append(to)
                visited[to] = True
    return visited

canGo = dfs(edges, 0)
canBack = dfs(edgesR, N - 1)

minDist = [10**18] * N
minDist[0] = 0
for i in range(N + 1):
    for fr, to, c in E:
        d = minDist[fr] + c
        if minDist[to] > d:
            if i == N and canGo[fr] and canBack[to]:
                print('-1')
                exit()
            minDist[to] = d

print(max(0, -minDist[N - 1]))

Solution (Python):
n, m, p = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for _ in range(m)]

for i in e:
    i[0] -= 1
    i[1] -= 1
    i[2] -= p

d = [-10**18] * n
ok1 = [False] * n
ok2 = [False] * n
d[0] = 0
ok1[0] = True
ok2[-1] = True

for _ in range(n):
    for a, b, c in e:
        if ok1[a]:
            d[b] = max(d[b], d[a] + c)
            ok1[b] = True
        if ok2[b]:
            ok2[a] = True
aa = d[:]

for _ in range(n):
    for a, b, c in e:
        if ok1[a]:
            d[b] = max(d[b], d[a] + c)
            ok1[b] = True
        if ok2[b]:
            ok2[a] = True

bb = d[:]

ok = False
for i in range(n):
    if ok1[i] and ok2[i]:
        if aa[i] != bb[i]:
            ok = True
if ok:
    print("-1")
else:
    print(max(aa[-1], 0))

Solution (Python):
from collections import deque


def bellman_ford(start: int, graph: list) -> list:
    """bellman-ford法: 始点startから各頂点への最短距離を求める(負辺OK)
    計算量: O(|E||V|)
    """
    INF = float("inf")
    n = len(graph)
    dist = [-INF] * n
    dist[start] = 0
    if n == 1:
        return False, [0]
    for _ in range(n - 1):
        update = False
        for v, edge in enumerate(graph):
            for nxt_v, cost in edge:
                if not (visited[nxt_v] and visited2[nxt_v]):
                    continue
                if dist[nxt_v] < dist[v] + cost:
                    dist[nxt_v] = dist[v] + cost
                    update = True
        if not update:
            break
    else:
        return True, dist
    return False, dist

def bellman_ford2(start: int, graph: list) -> list:
    """bellman-ford法: 始点startから各頂点への最短距離を求める(負辺OK)
    計算量: O(|E||V|)
    """
    INF = float("inf")
    n = len(graph)
    dist = [-INF] * n
    dist[start] = 0
    if n == 1:
        return False, [0]
    for _ in range(n + 100):
        update = False
        for v, edge in enumerate(graph):
            for nxt_v, cost in edge:
                if not (visited[nxt_v] and visited2[nxt_v]):
                    continue
                if dist[nxt_v] < dist[v] + cost:
                    dist[nxt_v] = dist[v] + cost
                    update = True
        if not update:
            break
    else:
        return True, dist
    return False, dist

n, m, p = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
rev_graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    cost -= p
    graph[a].append((b, cost))
    rev_graph[b].append((a, cost))

visited = [False] * n
def dfs():
    q = deque([0])
    visited[0] = True
    while q:
        v = q.pop()
        for nxt_v, _ in graph[v]:
            if visited[nxt_v]:
                continue
            visited[nxt_v] = True
            q.append(nxt_v)
dfs()

visited2 = [False] * n
def dfs2():
    q = deque([n - 1])
    visited2[n - 1] = True
    while q:
        v = q.pop()
        for nxt_v, _ in rev_graph[v]:
            if visited2[nxt_v]:
                continue
            visited2[nxt_v] = True
            q.append(nxt_v)
dfs2()




boolian, dist = bellman_ford(0, graph)
boolian, dist2 = bellman_ford2(0, graph)
if not boolian:
    print(max(dist[-1], 0))
else:
    for i in range(n):
        if dist[i] < dist2[i]:
            print(-1)
            exit()
    print(dist2[-1])

Solution (Python):


def glaph_bfs(s,n,e):
  Q=[s]
  visited={s}
  while Q:
    P=[]
    for i in Q:
      for j,_ in e[i]:
        if j in visited:continue
        visited.add(j)
        P.append(j)
    Q=P
  return visited
  



def find_negative_loop(n,e):
	d=n*[10**20];d[0]=0
	for h in range(n):
		for i,j,k in e:
			if d[j]>d[i]+k:
				d[j]=d[i]+k
				if h==n-1:return True
	return False




def bellman_ford(s,n,e):
  inf=10**20;d=[inf]*n;d[s]=0
  while 1:
    f=True
    for i,j,k in e:
      if d[i]!=inf and d[j]>d[i]+k:d[j]=d[i]+k;f=False
    if f:break
  return d

n,m,p=map(int,input().split())
edge=[[]for _ in range(n)]
edger=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  c-=p
  a-=1
  b-=1
  edge[a].append((b,c))
  edger[b].append((a,c))
visited=glaph_bfs(0,n,edge)
visitedr=glaph_bfs(n-1,n,edger)
for i in range(n):
  if not(i in visited and i in visitedr):edge[i]=[]
e=[]
for i in range(n):
  for j in range(len(edge[i])):e.append((i,edge[i][j][0],-edge[i][j][1]))
if find_negative_loop(n,e):print(-1);exit()
print(max(-bellman_ford(0,n,e)[n-1],0))

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M,P=map(int,input().split())
    edge=[]
    for _ in range(M):
        A,B,C=map(int1,input().split())
        C+=1
        edge.append((A,B,P-C))
    d=[INF]*N
    d[0]=0
    f=False
    for i in range(N*2):
        for a,b,c in edge:
            if d[b]>d[a]+c:
                if i<N-1:
                    d[b]=d[a]+c
                else:
                    if d[a]<10**17:
                        d[b]=-INF
                    if b==N-1:
                        f=True
    if f:
        print(-1)
    else:
        print(max(-d[N-1],0))

if __name__ == '__main__':
    main()

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

edges = []
toE = [[] for _ in range(N)]
frE = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges.append((fr, to, -(c - P)))
    toE[fr].append(to)
    frE[to].append(fr)

def getVisitedList(s, edges):
    visited = [False] * N
    st = [s]
    visited[s] = True
    while st:
        now = st.pop()
        for to in edges[now]:
            if not visited[to]:
                visited[to] = True
                st.append(to)
    return visited

canGo = getVisitedList(0, toE)
canBack = getVisitedList(N - 1, frE)

def sol():
    minDist = [10**18] * N
    minDist[0] = 0
    for i in range(N + 1):
        for fr, to, c in edges:
            d = minDist[fr] + c
            if minDist[to] > d:
                if i == N and canGo[fr] and canBack[to]:
                    return -1
                minDist[to] = d
    return max(0, -minDist[N - 1])

print(sol())

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

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

edges = [[] for _ in range(N)]
to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]

for a, b, c in X:
    a -= 1
    b -= 1
    c = -(c - P)
    edges[a].append((b, c))
    to[a].append(b)
    ot[b].append(a)

ok_1 = [False] * N
ok_n = [False] * N


def dfs(u):
    if ok_1[u]:
        return
    
    ok_1[u] = True
    for v in to[u]:
        dfs(v)
        
def rdfs(u):
    if ok_n[u]:
        return
    
    ok_n[u] = True
    for v in ot[u]:
        rdfs(v)
        
dfs(0)
rdfs(N - 1)
flag = [ok_1[i] & ok_n[i] for i in range(N)]


INF = 10 ** 9 + 7
d = [INF] * N
d[0] = 0
cnt = 0
updated = True
while updated and cnt <= N:
    updated = False
    cnt += 1
    for u in range(N):
        if not flag[u]:
            continue
        for v, c in edges[u]:
            if not flag[v]:
                continue

            value = d[u] + c
            if d[v] > d[u] + c:
                d[v] = value
                updated = True

if cnt > N:
    print(-1)
else:
    print(max(0, -d[-1]))

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    
    
    def BellmanFord(N, M, edges):
        
        inf=10**20
        d = [inf] * N
        d[0] = 0

        for i in range(N-1):
            for (u, v, c) in edges:
                if to[u] and to[v] and rto[u] and rto[v]:
                    if d[u] + c < d[v]:
                        d[v] = d[u] + c

        
        
        for (u, v, c) in edges:
            if to[u] and to[v] and rto[u] and rto[v]:
                if d[u] + c < d[v]:
                    return None
                
        return d[N-1]
    
    N,M,P=MI()
    edges=[]
    adj1=[[]for _ in range(N)]
    adj2=[[]for _ in range(N)]
    for _ in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        c-=P
        edges.append([a,b,-1*c])
        adj1[a].append(b)
        adj2[b].append(a)
        
    
    
    import queue
    q=queue.Queue()
    
    to=[0]*N
    to[0]=1
    rto=[0]*N
    rto[-1]=1
    
    q.put(0)
    while not q.empty():
        v=q.get()
        for nv in adj1[v]:
            if to[nv]==0:
                to[nv]=1
                q.put(nv)
                
    q.put(N-1)
    while not q.empty():
        v=q.get()
        for nv in adj2[v]:
            if rto[nv]==0:
                rto[nv]=1
                q.put(nv)
        
    
    
    
    ans=BellmanFord(N,M,edges)
    
    if ans==None:
        print(-1)
    elif ans>=10**10:
        print(-1)
    else:
        print(max(-1*ans,0))
    
        

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().strip()


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

    """
    あらかじめ各辺のコイン枚数からP引いておけば、求めるのは単純にコイン枚数の最大値となる。
    すなわちこれは「最長経路問題」に他ならない。
    するとコイン枚数を(-1)倍して「最短経路問題」を求めればよく典型問題に帰着。
        ダイクストラ　　　→　負辺があるのでダメ
        ベルマンフォード　→　O(VE)で解けるので今回はこれ
        ワ―シャルフロイド →　O(V^3)なので間に合わない

    ベルマンフォード復習：
        １．スタートする頂点をsとしてd[s] = 0、その他の頂点はd[v] = \inftyで初期化
        ２．重みwの辺u→vに対してd[v] = min(d[v], d[u] + w)
        ３．この更新を「すべての辺」（E本）に対して行う
        ４．２－３ステップをN（頂点数）回繰り返すと値の更新が（負閉路を除き）収束する
    
    ただし本問では負閉路検出後にそれが1-(負閉路)-Nのように頂点1と頂点Nの間にいることを
    確認する必要がある。
    """

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

    """
    後々必要なので、頂点0「から」たどり着ける頂点と、
    頂点(N-1)「に」たどり着ける頂点をそれぞれ列挙する
    """

    reachable_from_1 = [0] * N
    reachable_to_N = [0] * N
    ok = [0] * N 

    def dfs(v):
        if reachable_from_1[v]:
            return
        reachable_from_1[v] = 1
        for u in repn[v]:
            dfs(u)
    
    def reverse_dfs(v):
        if reachable_to_N[v]:
            return
        reachable_to_N[v] = 1
        for u in reverse_repn[v]:
            reverse_dfs(u)
    
    dfs(0)
    reverse_dfs(N - 1)
    for i in range(N):
        if reachable_from_1[i] and reachable_to_N[i]:
            ok[i] = 1

    """
    ここからベルマンフォード
    """

    d = [float("inf")] * N
    d[0] = 0
    step = 0
    update = True
    while update:
        update = False
        for i in range(M):
            a, b, cost = edges[i]
            if not ok[a]: continue
            if not ok[b]: continue
            new_cost = d[a] + cost
            if new_cost < d[b]:
                update = True
                d[b] = new_cost
        step += 1
        if step > N:
            print(-1)
            return
    print(max(0, -d[N - 1]))


if __name__ == "__main__":
    main()