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:
n,m,p = map(int,input().split())

edges=[[0 for _ in range(n)] for i in range(n)]

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

goal = n-1
coin = 0
visited = [0]*n
flag = [False]*n
q =[[0,0]] #node,coins
while True:
  crt = q.pop()
  visited[crt[0]] = crt[1]
  for i in range(n):
    if edges[crt[0]][i]>0:
      q.append([i,crt[1]+edges[crt[0]][i]])

Submission status: Runtime Error

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

G = [[] for i in range(N+1)]

costs = {}

def loop(v):
    print("loop")
    print(v)
    exit()

for i in range(M):
    a,b,c = map(int,input().split())
    c = c-P
    if a==b:
        if a == N:
            loop(-1)
        else:
            continue
    G[a].append(b)
    costs[(a,b)] = c

# print(G)

def bfs(node,depth,visited):
    val = -float("inf")
    # print(G[node],depth,visited)
    if len(G[node])==0:
        if node == N:
            return 0
        else:
            return val
    for n in G[node]:
        if n in visited:
            if val >=0:
                continue
            else:
                loop(-1)
        val = max(val,costs[node,n]+bfs(n,depth+1, tuple(visited+(n,))))
    return val

val = bfs(1,0,())

print(max(val,0))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)

from collections import deque

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


visited = [0] * n
def dfs(v):
    for u in edge[v]:
        if visited[u] == 0:
            visited[u] = 1
            dfs(u)
visited[0] = 1
dfs(0)
# print(visited)
flag = [vi for vi in visited]

def dfs2(v):
    for u in edge[v]:
        if u == n - 1:
            visited2[u] = 1
            break
        if visited2[u] == 0:
            visited2[u] = 1
            dfs2(u)

for i in range(1, n):
    if flag[i] == 0:
        continue
    visited2 = [0] * n
    visited2[i] = 1
    dfs2(i)
    if visited2[n-1] == 0 and flag[i] == 1:
        flag[i] = 0

# print(flag)
target_v = set([i for i in range(n) if flag[i] == 1])
# print(target_v)

q = deque()
visited3 = [0] * n
visited3[0] = 1
q.append((0, 0, visited3))
ans = [0] * n
iter = 0
impossible = False
while q:
    v, c, visited3 = q.popleft()
    for u in edge[v]:
        if u not in target_v:
            continue
        if visited3[u] == 0:
            ans[u] = c + coin[v][u]
            visited3[u] = 1
            q.append((u, c + coin[v][u]))
        else:
            if ans[u] <= c + coin[v][u]:
                impossible = True
                break

    if impossible:
        break

if impossible:
    print(-1)
else:
    print(max(0, ans[n-1]))

Submission status: Runtime Error

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

def main():
    N, M, P = map(int, input().split())
    g = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]
    data0 = [None] * (M+1)
    data1 = [None] * (M+1)
    data2 = [None] * (M+1)
    for i in range(M):
        a, b, c = map(int, input().split())
        data0[i] = a
        data1[i] = b
        data2[i] = c


    for i in range(M):
        g[data1[i]].append(data0[i])
        g2[data0[i]].append(data1[i])








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

    for i in range(N):
        d_N = [d[i] for i in range(1, N+1) if visit[i]]
        for j in range(M):
            d[data1[j]] = max(d[data1[j]], d[data0[j]]+data2[j]-P)
        if i == N-1:
            if d_N != [d[i] for i in range(1, N+1) if visit[i]]:
                ans = -1

            else:
                ans = d[N]

    if ans == -1:
        print(-1)
    else:
        print(max(0, ans))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def main():
    N, M, P = map(int, input().split())
    g = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]
    data0 = [None] * (M+1)
    data1 = [None] * (M+1)
    data2 = [None] * (M+1)
    for i in range(M):
        a, b, c = map(int, input().split())
        data0[i] = a
        data1[i] = b
        data2[i] = c


    for i in range(M):
        g[data1[i]].append(data0[i])
        g2[data0[i]].append(data1[i])

    visit = [False]*(N+1)
    visit2 = [False]*(N+1)

    queue = [N]
    while len(queue) > 0:
        nextqueue = []
        for now in queue:
            visit[now] = True
            for next in g[now]:
                if not visit[next]:
                    nextqueue.append(next)
        queue = nextqueue[:]

    queue = [1]
    while len(queue) > 0:
        nextqueue = []
        for now in queue:
            visit2[now] = True
            for next in g2[now]:
                if not visit2[next]:
                    nextqueue.append(next)
        queue = nextqueue[:]




    for i in range(1, N+1):
        visit[i] = visit[i] and visit2[i]


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



    if ans == -1:
        print(-1)
    else:
        print(max(0, ans))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

def dfs(p, dis, maxd):
    for q, d in graph[p]:
        if q == p:
            continue
        if q == N-1:
            if dis+d > maxd:
                maxd = dis+d
            return maxd
        maxd = dfs(q, dis+d, maxd)
    return maxd

ans = dfs(0, 0, 0)
for q, d in graph[N-1]:
    if N-1 == q:
        ans = -1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m,p=map(int,input().split())
edge = [[] for i in range(m)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[i]=[a-1,b-1,-c+p]

def sp(s,n,w,es):
  d=[float("inf")]*n
  d[s]=0
  count=0
  ret=[]
  while count<n+1:
    update=False
    for i in range(w):
      e=es[i]
      if d[e[0]]!=float("inf") and d[e[1]]>d[e[0]]+e[2]:
        d[e[1]]=d[e[0]]+e[2]
        update=True
    if not update:
      ret.append(d[-1])
      ret.append(d[-1])
      break
    count+=1
    if count>=n-1:
      ret.append(d[-1])
  return ret
d1,d2=sp(0,n,m,edge)
print(-1 if d1!=d2 else max(0,-d2))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import networkx as nx


def solve(N: int, M: int, P: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    G = nx.DiGraph()
    G.add_nodes_from(range(1, N+1))
    for e in range(M):
        G.add_edge(A[e], B[e], weight = P - C[e])
    try:
        length = nx.bellman_ford_path_length(G,1,N)
        print(max(-length, 0))
    except nx.NetworkXUnbounded:
        cycles = nx.simple_cycles(G)
        for cycle in cycles:
            if (1 in cycle) or (N in cycle):
                print(-1)
                return
            else: 
                G.remove_nodes_from(cycle)
        
        length = nx.bellman_ford_path_length(G,1,N)
        print(max(-length, 0))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]" 
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, P, A, B, C)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M, P = map(int, input().split())
E = [[] for _ in range(N)]
RE = [[] for _ in range(N)]
for _ in range(M):
  a, b, c = map(int, input().split())
  E[a - 1].append([b - 1, c])
  RE[b - 1].append(a - 1)
Reachable = [[False, False] for _ in range(N)]
Q = [0]
while(Q):
  q = Q.pop(0)
  Reachable[q][0] = True
  for adj, _ in E[q]:
    if not Reachable[adj][0]:
      Q.append(adj)
Q = [N - 1]
while(Q):
  q = Q.pop(0)
  Reachable[q][1] = True
  for adj in RE[q]:
    if not Reachable[adj][1]:
      Q.append(adj)
R = [r[0] and r[1] for r in Reachable]
C = [None] * N
C[0] = 0
A = [0, 0]
def DFS(s):
  if A[1] != 0:
    return 0
  if s == N - 1:
    A[0] = max(C[s], A[0])
  for adj, coin in E[s]:
    if not R[s]:
      continue
    if C[adj] == None:
      C[adj] = C[s] + coin - P
      DFS(adj)
      C[adj] = None
    elif C[adj] < C[s] + coin - P:
      A[1] = -1
      return 0
DFS(0)
if A[1] != 0:
  print(-1)
else:
  print(A[0])

Submission status: Runtime Error

Solution code:
import math
import copy

n,m,p=map(int, input().split())
abc={}
for i in range(m):
    a,b,c=map(int, input().split())
    if not a in abc:
        abc[a] = [[b, c]]
    else:
        abc[a].append([b, c])

def func(now, sumcoin, memo):
    if not now in memo:
        memo[now]=sumcoin
    elif sumcoin > memo[now]:
        return -1

    if not now in abc and now == n:
        return max(0, sumcoin)

    if not now in abc:
        return -1
    
    ret=-1
    for next, coin in abc[now]:
        ret=max(ret, func(next, coin+sumcoin-10, copy.copy(memo)))
    
    return ret

print(func(1, 0, {}))

Submission status: Runtime Error

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

E = [[0, 0, 0] for n in range(M)]
for n in range(N):
    A, B, C = map(int, input().split())
    E[n][0] = A - 1
    E[n][1] = B - 1
    E[n][2] = P - C


def BellmanFord(edges, num_v, source, end):
    inf = 10 ** 8
    dist = [inf for i in range(num_v)]
    dist[source] = 0

    for i in range(num_v):
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]

    end1 = dist[end]
    for i in range(num_v):
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]

    end2 = dist[end]

    return max(0, -end1) if end1 == end2 else -1


res = BellmanFord(E, N, 0, N - 1)
print(res)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m,p=map(int,input().split())
edge = [[] for i in range(m)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[i]=[a-1,b-1,-c+p]

def sp(s,n,w,es):
  d=[float("inf")]*n
  d[s]=0
  count=0
  ret=[]
  while count<n:
    update=False
    for i in range(w):
      e=es[i]
      if d[e[0]]!=float("inf") and d[e[1]]>d[e[0]]+e[2]:
        d[e[1]]=d[e[0]]+e[2]
        update=True
    if not update:
      break
    count+=1
    if count>=n-1:
      ret.append(d[-1])
  return ret
d1,d2=sp(0,n,m,edge)
print(-1 if d1!=d2 else max(0,-d2))

Submission status: Runtime Error

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

E = [[0, 0, 0] for n in range(M)]
for n in range(N):
    A, B, C = map(int, input().split())
    E[n][0] = A - 1
    E[n][1] = B - 1
    E[n][2] = P - C


def BellmanFord(edges, num_v, source, end):
    inf = float("inf")
    dist = [inf for i in range(num_v)]
    dist[source] = 0

    for i in range(num_v):
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]

    end1 = dist[end]
    for i in range(num_v):
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]

    end2 = dist[end]

    return max(0, -end1) if end1 == end2 else -1


res = BellmanFord(E, N, 0, N - 1)
print(res)

Submission status: Runtime Error

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

from itertools import accumulate
from bisect import bisect, bisect_left
from collections import Counter, deque, defaultdict
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor
from string import ascii_lowercase as abc

from sys import setrecursionlimit
setrecursionlimit(10**9)
 
import sys
#input = sys.stdin.readline
from collections import Counter
def inpl(): return list(map(int, input().split()))

N, M, P = inpl()
INF = 10**12
G = [[] for _ in range(N)]
E = []
G2 = [[] for _ in range(N)]
rG2 = [[] for _ in range(N)]
for _ in range(N):
    a, b, c = inpl()
    G[a-1].append([b-1, -c+P])
    G2[a-1].append(b-1)
    rG2[b-1].append(a-1)
    E.append([a-1, b-1, -c+P])


def SCC(G, rG):
    N = len(G)
    def dfs(i):
        nonlocal t, rorder, searched
        searched[i] = True
        for j in G[i]:
            if not searched[j]:
                dfs(j)
        rorder[t] = i
        t += 1

    def rdfs(i):
        nonlocal t, group, g
        group[i] = g
        for j in rG[i]:
            if group[j] == -1:
                rdfs(j)

    t = 0
    rorder = [-1]*N
    searched = [0]*N
    group = [-1]*N

    for i in range(N):
        if not searched[i]:
            dfs(i)
    g = 0
    for i in range(N-1, -1, -1):
        if group[rorder[i]] == -1:
            rdfs(rorder[i])
            g += 1
    return group, g


def belman_ford(V, edges, r):
    "If glaph contains negative cycles then return True"
    D = [INF]*(V)
    D[r] = 0
    if V == 1:
        return False, [0]
    OK = True
    for _ in range(V-1):
        update = False
        for s, t, d in edges:
            if D[t] > D[s] + d:
                D[t] = D[s] + d
                update = True
        if not update:
            OK = False
    return OK, D

group, gsize = SCC(G2, rG2)
groups = [[] for _ in range(gsize)]
for i in range(N):
    groups[group[i]].append(i)

score = [10**12 for _ in range(N)]
negative_groups = [0]*N


for g in range(gsize):
    ggs = set(groups[g])
    for s in ggs:
        score[s] = 0
        Q = deque([s])
        while Q:
            p = Q.popleft()
            for q, c in G[p]:
                if not q in ggs:
                    continue
                if score[p] + c < score[q]:
                    score[q] = score[p] + c
                    Q.append(q)
            if score[s] < 0:
                negative_groups[s] = 1
                break

s = 0
Q = deque([s])
reach1 = [0]*N
reach1[0] = 1

while Q:
    p = Q.popleft()
    for q in G2[p]:
        if not reach1[q]:
            reach1[q] = 1
            Q.append(q)

s = N-1
Q = deque([s])
reachN = [0]*N
reachN[-1] = 1

while Q:
    p = Q.popleft()
    for q in rG2[p]:
        if not reachN[q]:
            reachN[q] = 1
            Q.append(q)

NEGATIVE, D = belman_ford(N, E, 0)

if any([reach1[i]&reachN[i]&negative_groups[i] for i in range(N)]) or reach1[-1]==0:
    print(-1)
else:
    print(max(0, -D[-1]))

Submission status: Runtime Error

Solution code:
n,m,p = (int(num) for num in input().split())
g = [[] for _ in range(n)]
h = [[] for _ in range(n)]
for i in range(m):
    at,bt,ct = (int(num) for num in input().split())
    itemg = [bt-1,ct-p]
    itemh = [at-1,ct-p]
    g[at-1].append(itemg)
    h[at-1].append(itemh)
#print(g)
visitg = [1] + [0]*(n-1)
visith = [0]*(n-1) + [1]

score = [0] * n
score_next = [0] * n
for _ in range(n):
    score_next = [0] * n
    for i in range(n):
        if visitg[i] == 1:
            s = score[i]
            for e in g[i]:
                visitg[e[0]] = 1 
                t = score_next[e[0]]
                if t < s + e[1]:
                    score_next[e[0]] = s + e[1]
    score = score_next.copy()

scoren = score.copy()

for _ in range(n):
    score_next = [0] * n
    for i in range(n):
        if visitg[i] == 1:
            s = score[i]
            for e in g[i]:
                visitg[e[0]] = 1 
                t = score_next[e[0]]
                if t < s + e[1]:
                    score_next[e[0]] = s + e[1]
    score = score_next.copy()
    
if scoren[-1] < score[-1]:
    print(-1)
else:
    print(max(0,scoren[-1]))

Submission status: Runtime Error

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

from itertools import accumulate
from bisect import bisect, bisect_left
from collections import Counter, deque, defaultdict
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor
from string import ascii_lowercase as abc

from sys import setrecursionlimit
setrecursionlimit(10**9)
 
import sys
#input = sys.stdin.readline
from collections import Counter
def inpl(): return list(map(int, input().split()))

N, M, P = inpl()
INF = 10**12
G = [[] for _ in range(N)]
E = []
G2 = [[] for _ in range(N)]
rG2 = [[] for _ in range(N)]
for _ in range(N):
    a, b, c = inpl()
    G[a-1].append([b-1, -c+P])
    G2[a-1].append(b-1)
    rG2[b-1].append(a-1)
    E.append([a-1, b-1, -c+P])


def SCC(G, rG):
    N = len(G)
    def dfs(i):
        nonlocal t, rorder, searched
        searched[i] = True
        for j in G[i]:
            if not searched[j]:
                dfs(j)
        rorder[t] = i
        t += 1

    def rdfs(i):
        nonlocal t, group, g
        group[i] = g
        for j in rG[i]:
            if group[j] == -1:
                rdfs(j)

    t = 0
    rorder = [-1]*N
    searched = [0]*N
    group = [-1]*N

    for i in range(N):
        if not searched[i]:
            dfs(i)
    g = 0
    for i in range(N-1, -1, -1):
        if group[rorder[i]] == -1:
            rdfs(rorder[i])
            g += 1
    return group, g


def belman_ford(V, edges, r):
    "If glaph contains negative cycles then return True"
    D = [INF]*(V)
    D[r] = 0
    if V == 1:
        return False, [0]
    OK = True
    for _ in range(V-1):
        update = False
        for s, t, d in edges:
            if D[t] > D[s] + d:
                D[t] = D[s] + d
                update = True
        if not update:
            OK = False
    return OK, D

group, gsize = SCC(G2, rG2)
groups = [[] for _ in range(gsize)]
for i in range(gsize):
    groups[group[i]].append(i)

score = [10**12 for _ in range(N)]
negative_groups = [0]*N


for g in range(gsize):
    ggs = set(groups[g])
    for s in ggs:
        score[s] = 0
        Q = deque([s])
        while Q:
            p = Q.popleft()
            for q, c in G[p]:
                if not q in ggs:
                    continue
                if score[p] + c < score[q]:
                    score[q] = score[p] + c
                    Q.append(q)
            if score[s] < 0:
                negative_groups[s] = 1
                break

s = 0
Q = deque([s])
reach1 = [0]*N
reach1[0] = 1

while Q:
    p = Q.popleft()
    for q in G2[p]:
        if not reach1[q]:
            reach1[q] = 1
            Q.append(q)

s = N-1
Q = deque([s])
reachN = [0]*N
reachN[-1] = 1

while Q:
    p = Q.popleft()
    for q in rG2[p]:
        if not reachN[q]:
            reachN[q] = 1
            Q.append(q)

NEGATIVE, D = belman_ford(N, E, 0)

if any([reach1[i]&reachN[i]&negative_groups[i] for i in range(N)]) or reach1[-1]==0:
    print(-1)
else:
    print(max(0, -D[-1]))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def BellmanFord(g, s):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = set(V)

    dist = defaultdict(lambda: sys.maxsize)
    pred = defaultdict(lambda: -1)

    dist[s] = 0

    N = len(V)
    for i in range(N+1):
        for u in g:
            for v in g[u]:
                if dist[v] > dist[u] + g[u][v]:
                    if i == N:
                        return 'inf'
                    dist[v] = dist[u] + g[u][v]
                    pred[v] = u
    return dist


@mt
def slv(N, M, P, ABC):

    g =defaultdict(dict)
    for a, b, c in ABC:
        g[a][b] = -(c - P)

    def r(s):
        q = [s]
        done = set()
        done.add(s)
        while q:
            v = q.pop()
            for u in g[v]:
                done.add(u)
        return N in done, done
    
    _, r1 = r(1)
    for i in range(2, N):
        if i not in r1:
            g.pop(i)

    d = set()
    for i in range(2, N):
        a, _ = r(i)
        d.add(i)
    
    for i in d:
        g.pop(i)
    for k, v in g.items():
        for i in d:
            if i in v:
                v.pop(i)

    d = BellmanFord(g, 1)
    if d == 'inf':
        return -1
    return max(0, -d[N])


def main():
    N, M, P = read_int_n()
    ABC = [read_int_n() for _ in range(M)]
    print(slv(N, M, P, ABC))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,m,p = (int(num) for num in input().split())
g = [[] for _ in range(n)]
h = [[] for _ in range(n)]
for i in range(m):
    at,bt,ct = (int(num) for num in input().split())
    itemg = [bt-1,ct-p]
    itemh = [at-1,ct-p]
    g[at-1].append(itemg)
    h[at-1].append(itemh)
#print(g)
visitg = [1] + [0]*(n-1)
visith = [0]*(n-1) + [1]

score = [0] * n
score_next = [0] * n
for _ in range(n):
    for i in range(n):
        if visitg[i] == 1:
            s = score[i]
            for e in g[i]:
                visitg[e[0]] = 1 
                t = score_next[e[0]]
                if t < s + e[1]:
                    score_next[e[0]] = s + e[1]
    score = score_next.copy()

scoren = score.copy()

for _ in range(n):
    for i in range(n):
        if visitg[i] == 1:
            s = score[i]
            for e in g[i]:
                visitg[e[0]] = 1 
                t = score_next[e[0]]
                if t < s + e[1]:
                    score_next[e[0]] = s + e[1]
    score = score_next.copy()
    
if scoren[-1] < score[-1]:
    print(-1)
else:
    print(max(0,scoren[-1]))

Submission status: Runtime Error

Solution code:
#include <cstdio>

typedef long long int64;

int n, m, p, now;
int64 ans;
int f[5555], t[5555], v[5555], d[2][5555];

void go() {
  auto &d_now = d[now % 2];
  auto &d_next = d[(now + 1) % 2];
  int64 tmp = 1LL * d_now[n] - 1LL * p * now;
  if (tmp > ans) {
    ans = tmp;
  }
  for (int i = 0; i <= n; i++) d_next[i] = -1E9;
  for (int i = 0; i < m; i++) {
    int ff = f[i], tt = t[i], vv = v[i];
    if (d_now[ff] + vv > d_next[tt]) {
      d_next[tt] = d_now[ff] + vv;
    }
  }
}

int main() {
  scanf("%d%d%d", &n, &m, &p);
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", f + i, t + i, v + i);
  }
  for (int i = 0; i <= n; i++) {
    d[0][i] = d[1][i] = -1E9;
  }
  d[0][1] = 0;
  for (int i = 0; i < n + n + 10; i++) {
    go();
    now += 1;
  }

  int64 maybe_ans = ans;
  if (maybe_ans <= 0) {
    printf("0\n");
    return 0;
  }

  for (int i = 0; i < n + 10; i++) {
    go();
    now += 1;
  }

  if (ans > maybe_ans) {
    printf("-1\n");
  } else {
    printf("%lld\n", maybe_ans);
  }

  return 0;
}

Submission status: Runtime Error

Solution code:
N,M,P = map(int,input().split())
side = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    side[a-1].append([b-1,c-P])
node = [-float('inf')]*N
node[0] = 0

def DFS(p,l):
    if node[p] == float('inf'):
        return
    elif p in l:
        node[p] = float('inf')
        for i,v in side[p]:
            DFS(i,l+[p])
    else:
        for i,v in side[p]:
            if node[i] < node[p]+v:
                node[i] = node[p]+v
                DFS(i,l+[p])
    return

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

Submission status: Runtime Error

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

from itertools import accumulate
from bisect import bisect, bisect_left
from collections import Counter, deque, defaultdict
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor
from string import ascii_lowercase as abc

from sys import setrecursionlimit
setrecursionlimit(10**9)
 
import sys
#input = sys.stdin.readline
from collections import Counter
def inpl(): return list(map(int, input().split()))

N, M, P = inpl()
INF = 10**12
G = [[] for _ in range(N)]
E = []
G2 = [[] for _ in range(N)]
rG2 = [[] for _ in range(N)]
for _ in range(N):
    a, b, c = inpl()
    G[a-1].append([b-1, -c+P])
    G2[a-1].append(b-1)
    rG2[b-1].append(a-1)
    E.append([a-1, b-1, -c+P])


def SCC(G, rG):
    N = len(G)
    def dfs(i):
        nonlocal t, rorder, searched
        searched[i] = True
        for j in G[i]:
            if not searched[j]:
                dfs(j)
        rorder[t] = i
        t += 1

    def rdfs(i):
        nonlocal t, group, g
        group[i] = g
        for j in rG[i]:
            if group[j] == -1:
                rdfs(j)

    t = 0
    rorder = [-1]*N
    searched = [0]*N
    group = [-1]*N

    for i in range(N):
        if not searched[i]:
            dfs(i)
    g = 0
    for i in range(N-1, -1, -1):
        if group[rorder[i]] == -1:
            rdfs(rorder[i])
            g += 1
    return group, g


def belman_ford(V, edges, r):
    "If glaph contains negative cycles then return True"
    D = [INF]*(V)
    D[r] = 0
    if V == 1:
        return False, [0]
    OK = True
    for _ in range(V-1):
        update = False
        for s, t, d in edges:
            if D[t] > D[s] + d:
                D[t] = D[s] + d
                update = True
        if not update:
            OK = False
    return OK, D

group, gsize = SCC(G2, rG2)
groups = [[] for _ in range(gsize)]
for i in range(N):
    groups[group[i]].append(i)

score = [10**12 for _ in range(N)]
negative_groups = [0]*N


for g in range(gsize):
    ggs = set(groups[g])
    s = groups[g][0]
    score[s] = 0
    Q = deque([s])
    while Q:
        p = Q.popleft()
        for q, c in G[p]:
            if not q in ggs:
                continue
            if score[p] + c < score[q]:
                score[q] = score[p] + c
                Q.append(q)
        if score[s] < 0:
            for g in ggs:
                negative_groups[g] = 1
            break

s = 0
Q = deque([s])
reach1 = [0]*N
reach1[0] = 1

while Q:
    p = Q.popleft()
    for q in G2[p]:
        if not reach1[q]:
            reach1[q] = 1
            Q.append(q)

s = N-1
Q = deque([s])
reachN = [0]*N
reachN[-1] = 1

while Q:
    p = Q.popleft()
    for q in rG2[p]:
        if not reachN[q]:
            reachN[q] = 1
            Q.append(q)

NEGATIVE, D = belman_ford(N, E, 0)

if any([reach1[i]&reachN[i]&negative_groups[i] for i in range(N)]) or reach1[-1]==0:
    print(-1)
else:
    print(max(0, -D[-1]))