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: Time Limit Exceeded

Solution code:
import sys


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


n, m, p = map(int, input().split())
edge0 = []
d = [[] for i in range(n)]
for i in range(m):
    ai, bi, ci = map(int, input().split())
    edge0.append((bi-1,ai-1,-ci+p))
    d[ai-1] += [bi-1]


p0 = [False for i in range(n)]
p0[0] = True
from collections import deque
q = deque([0])
while len(q)>0:
    x = q.popleft()
    for y in d[x]:
        if not p0[y]:
            p0[y] = True
            q.append(y)

edge = []
for e in edge0:
    if p0[e[1]] and p0[e[0]]:
        edge += [e]
dist = [float("inf") for i in range(n)]
dist[n-1] = 0
h = False
for i in range(n):
    updated = False
    for e in edge:
        if dist[e[1]] > dist[e[0]] + e[2] and p0[e[1]] and p0[e[0]]:
            dist[e[1]] = dist[e[0]] + e[2]
            updated = True
    if not updated:
        break
else:
    h = True

if h:
    print(-1)
else:
    print(max(0, -dist[0]))

Submission status: Time Limit Exceeded

Solution code:
n, m, p = map(int, input().split())
edge = []
d = [[] for i in range(n)]
for i in range(m):
    ai, bi, ci = map(int, input().split())
    edge.append((bi-1,ai-1,-ci+p))
    d[ai-1] += [bi-1]


p0 = [False for i in range(n)]
p0[0] = True
from collections import deque
q = deque([0])
while len(q)>0:
    x = q.popleft()
    for y in d[x]:
        if not p0[y]:
            p0[y] = True
            q.append(y)

dist = [float("inf") for i in range(n)]
dist[n-1] = 0
h = False
for i in range(n):
    updated = False
    for e in edge:
        if dist[e[1]] > dist[e[0]] + e[2] and p0[e[1]] and p0[e[0]]:
            dist[e[1]] = dist[e[0]] + e[2]
            updated = True
    if not updated:
        break
else:
    h = True

if h:
    print(-1)
else:
    print(max(0, -dist[0]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)

def dfs(i):
	if i in use:
		return 
	use.add(i)
	for e in edges_r[i]:
		dfs(e)

def bf():
	d = [float('inf') for _ in range(n + 1)]
	d[1] = 0
	for _ in range(n):
		f = False
		for e in edges_f:
			if d[e[1]] > d[e[0]] + e[2]:
				d[e[1]] = d[e[0]] + e[2]
				f = True	
		if not f:
			return max(0, -1 * d[n])
	return -1

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

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

use = set()
dfs(n)

edges_f = [e for e in edges_f if e[0] in use and e[1] in use]
print(bf())

Submission status: Time Limit Exceeded

Solution code:
import sys
from queue import Queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

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

A = [-1]*M
B = [-1]*M
C = [-1]*M
nodes_edges = [[] for _ in range(N)]
rev_nodes_edges = [[] for _ in range(N)]
coin = [-float('inf')]*N
coin[0] = 0
availables = set()

for edge in range(M):
    a, b, c = map(int, input().split())
    A[edge] = a-1
    B[edge] = b-1
    C[edge] = c-P
    nodes_edges[a-1].append(edge)
    rev_nodes_edges[b-1].append(edge)

def cut_graph(node):
    edges = rev_nodes_edges[node]
    availables.add(node)
    for edge in edges:
        prev = A[edge]
        if prev in availables:
            continue
        cut_graph(prev)

cut_graph(N-1)
q = Queue()
q.put(0)
count = 0
limit = M*(1+len(availables))
while not q.empty():
    if count == limit:
        print(-1)
        break
    node = q.get()
    edges = nodes_edges[node]
    for edge in edges:
        nxt = B[edge]
        if nxt not in availables:
            continue
        new_coin = C[edge]+coin[node]
        if new_coin > coin[nxt]:
            coin[nxt] = new_coin
            q.put(nxt)
    count += 1
else:
    ans = coin[N-1]
    ans = 0 if ans < 0 else ans
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from queue import Queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

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

A = [-1]*M
B = [-1]*M
C = [-1]*M
nodes_edges = [[] for _ in range(N)]
rev_nodes_edges = [[] for _ in range(N)]
coin = [-float('inf')]*N
coin[0] = 0
availables = set()

for edge in range(M):
    a, b, c = map(int, input().split())
    A[edge] = a-1
    B[edge] = b-1
    C[edge] = c-P
    nodes_edges[a-1].append(edge)
    rev_nodes_edges[b-1].append(edge)

def cut_graph(node):
    edges = rev_nodes_edges[node]
    availables.add(node)
    for edge in edges:
        prev = A[edge]
        if prev in availables:
            continue
        cut_graph(prev)

cut_graph(N-1)
q = Queue()
q.put(0)
count = 0
limit = len(availables) + N * M
while not q.empty():
    if count == limit:
        print(-1)
        break
    node = q.get()
    edges = nodes_edges[node]
    for edge in edges:
        nxt = B[edge]
        if nxt not in availables:
            continue
        new_coin = C[edge]+coin[node]
        if new_coin > coin[nxt]:
            coin[nxt] = new_coin
            q.put(nxt)
    count += 1
else:
    ans = coin[N-1]
    ans = 0 if ans < 0 else ans
    print(ans)

Submission status: Time Limit Exceeded

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

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


visited = [0] * n
def dfs(v):
    for u in edge_inv[v]:
        if visited[u] == 0:
            visited[u] = 1
            dfs(u)

visited[n-1] = 1
dfs(n-1)
target_nodes = [i for i in range(n) if visited[i]]

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    update = False
    for v_from, v_to, cost in edge:
        if v_from not in target_nodes or v_to not in target_nodes:
            continue
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            update = True
            d[v_to] = d[v_from] + cost


if update:
    print(-1)
else:
    print(max(0, -d[n-1]))

Submission status: Time Limit Exceeded

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

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


visited = [False] * n
def dfs(v):
    for u in edge_inv[v]:
        if not visited[u]:
            visited[u] = True
            dfs(u)

visited[n-1] = True
dfs(n-1)
target_nodes = [i for i in range(n) if visited[i]]

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    update = False
    for v_from, v_to, cost in edge:
        if v_from not in target_nodes or v_to not in target_nodes:
            continue
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            update = True
            d[v_to] = d[v_from] + cost


if update:
    print(-1)
else:
    print(max(0, -d[n-1]))

Submission status: Time Limit Exceeded

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

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


visited = [False] * n
def dfs(v):
    global visited
    for u in edge_inv[v]:
        if not visited[u]:
            visited[u] = True
            dfs(u)

visited[n-1] = True
dfs(n-1)
target_nodes = [i for i in range(n) if visited[i]]

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    update = False
    for v_from, v_to, cost in edge:
        if v_from not in target_nodes or v_to not in target_nodes:
            continue
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            update = True
            d[v_to] = d[v_from] + cost


if update:
    print(-1)
else:
    print(max(0, -d[n-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


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


visited = [False] * n
def dfs(v):
    for u in edge_inv[v]:
        if not visited[u]:
            visited[u] = True
            dfs(u)

visited[n-1] = True
dfs(n-1)
target_nodes = [i for i in range(n) if visited[i]]


INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    update = False
    for v_from, v_to, cost in edge:
        if v_from not in target_nodes or v_to not in target_nodes:
            continue
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            update = True
            d[v_to] = d[v_from] + cost


if update:
    print(-1)
else:
    print(max(0, -d[n-1]))

Submission status: Time Limit Exceeded

Solution code:
# n, m, p = map(int, input().split())
 
# n, m, p = 4, 5, 10
# arr = [[1, 2, 1], [1, 4, 1], [3, 4, 1], [2, 2, 100], [3, 3, 100]]

# n, m, p = 2, 2, 10
# arr = [(1, 2, 100), (2, 2, 100)]

n, m, p = map(int, input().split())
# arr = [(1, 2, 20), (2, 3, 30), (1, 3, 45)]

# n, m, p = 3, 4, 99999
# arr= [(1, 3, 8), (3, 2, 10), (2, 2, 100000), (2, 1, 3)]

abc = []
# edge = [[] for _ in range(n)]
rev_edge = [[] for _ in range(n)]

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

def dfs(e, s):
	v_set = {s, }
	stack = [s]

	while stack:
		v = stack.pop()
		for next_v in e[v]:
			if not next_v in v_set:
				stack.append(next_v)
				v_set.add(next_v)
	return v_set

def bellman_ford(sub_abc, n):
	dist = [float('inf')]*n 
	dist[0] = 0

	for _ in range(n):
		updated = False
		for ele in sub_abc:
			a, b, d = ele
			if dist[a] + d < dist[b]:
				dist[b] = dist[a] + d 
				updated = True
		if not updated:
			break
	else:
		return -1

	return max(-dist[n-1], 0)

use = dfs(rev_edge, n-1)
print(bellman_ford([(a, b, c) for a, b, c in abc if a in use and b in use], n))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

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

A = [-1]*M
B = [-1]*M
C = [-1]*M
back_edges = [[] for _ in range(N)]
forward_edges = [[] for _ in range(N)]
fb = [0]*N
past = set()
availables = set()

for edge in range(M):
    a, b, c = map(int, input().split())
    A[edge] = a-1
    B[edge] = b-1
    C[edge] = c-P
    forward_edges[a-1].append(edge)
    back_edges[b-1].append(edge)

def forward(node):
    if node in availables:
        return
    availables.add(node)
    edges = forward_edges[node]
    past.add(node)
    for edge in edges:
        forward(B[edge])
    past.discard(node)

forward(0)

def back(node):
    edges = back_edges[node]
    past.add(node)
    coin = -float('inf') if node != 0 else 0
    for edge in edges:
        a = A[edge]
        if a not in availables:
            continue
        c = C[edge]
        if a in past:
            if fb[a] < c + fb[node]:
                print(-1)
                sys.exit()
            continue
        fb[a] = c + fb[node]
        coin = max(back(a)+c, coin)
    past.discard(node)
    return coin

ans = back(N-1)
ans = 0 if ans < 0 else ans
print(ans)

Submission status: Time Limit Exceeded

Solution code:

n, m, p = map(int, input().split())
arr = [0]*(m)
for i in range(m):
	arr[i] = tuple(map(int, input().split()))
# n, m, p = 4, 5, 10
# arr = [[1, 2, 1], [1, 4, 1], [3, 4, 1], [2, 2, 100], [3, 3, 100]]

# n, m, p = 2, 2, 10
# arr = [(1, 2, 100), (2, 2, 100)]

# n, m, p = 3, 3, 10
# arr = [(1, 2, 20), (2, 3, 30), (1, 3, 45)]

dist = [float('inf')]*(n+1)

dist[1] = 0
parent = [-1]*(n+1)
for k in range(n-1):
	for i in range(m):
		u, v, c = arr[i]
		c = max(c-p, 0)
		if dist[u] - c < dist[v]:
			dist[v] = dist[u] - c
			if v != u: parent[v] = u
path = []
end = n
while parent[end] != -1:
	path.append(end)
	end = parent[end]
# print(parent)	
# print(dist)
path.append(1)
path.reverse()
old_dist = list(dist)

for i in range(m):
	u, v, c = arr[i]
	c = max(c-p, 0)
	if old_dist[u] - c < dist[v]:
		old_dist[v] = old_dist[u] - c
# print(old_dist)
for ele in path:
	if old_dist[ele] != dist[ele]:
		neg_cycle = True
		break
	neg_cycle = False

if neg_cycle:
	print(-1)
else:
	print(-1 if n not in path else -dist[n])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

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

A = [-1]*M
B = [-1]*M
C = [-1]*M
back_edges = [[] for _ in range(N)]
forward_edges = [[] for _ in range(N)]
fb = [0]*N
past = set()
availables = set()

for edge in range(M):
    a, b, c = map(int, input().split())
    A[edge] = a-1
    B[edge] = b-1
    C[edge] = c-P
    forward_edges[a-1].append(edge)
    back_edges[b-1].append(edge)

def forward(node):
    if node in past:
        return
    availables.add(node)
    edges = forward_edges[node]
    past.add(node)
    for edge in edges:
        forward(B[edge])
    past.discard(node)

forward(0)

def back(node):
    edges = back_edges[node]
    past.add(node)
    coin = -float('inf') if node != 0 else 0
    for edge in edges:
        a = A[edge]
        if a not in availables:
            continue
        c = C[edge]
        if a in past:
            if fb[a] < c + fb[node]:
                print(-1)
                sys.exit()
            continue
        fb[a] = c + fb[node]
        coin = max(back(a)+c, coin)
    past.discard(node)
    return coin

ans = back(N-1)
ans = 0 if ans < 0 else ans
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

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

A = [-1]*M
B = [-1]*M
C = [-1]*M
back_edges = [[] for _ in range(N)]
forward_edges = [[] for _ in range(N)]
fb = [0]*N
past = set()
availables = set()

for edge in range(M):
    a, b, c = map(int, input().split())
    A[edge] = a-1
    B[edge] = b-1
    C[edge] = c-P
    forward_edges[a-1].append(edge)
    back_edges[b-1].append(edge)

def forward(node):
    if node in past:
        return
    availables.add(node)
    edges = forward_edges[node]
    past.add(node)
    for edge in edges:
        forward(B[edge])
    past.discard(node)

forward(0)

def back(node):
    edges = back_edges[node]
    past.add(node)
    coin = -float('inf') if node != 0 else 0
    for edge in edges:
        a = A[edge]
        if a not in availables:
            continue
        c = C[edge]
        if a in past:
            if fb[a] < c + fb[node]:
                print(-1)
                sys.exit()
                continue
        fb[a] = c + fb[node]
        coin = max(back(a)+c, coin)
    past.discard(node)
    return coin

ans = back(N-1)
ans = 0 if ans < 0 else ans
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
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)]
    data = [list(map(int, input().split())) for _ in range(M)]
    for a, b, _ in data:
        g2[b].append(a)
        g[a].append(b)

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

    q = queue.Queue()
    q.put(1)
    visit[1] = True
    while (not q.empty()):
        now = q.get()
        for next in g[now]:
            if not visit[next]:
                visit[next] = True
                q.put(next)

    q = queue.Queue()
    q.put(N)
    visit2[N] = True
    while (not q.empty()):
        now = q.get()
        for next in g2[now]:
            if not visit2[next]:
                visit2[next] = True
                q.put(next)

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


    INF = 1000000001
    d = [(-1)*INF for i in range(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):
            a = data[j][0]
            b = data[j][1]
            c = data[j][2]
            d[b] = max(d[b], d[a]+c-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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]

# エントリーポイント
def main():
    N, M, P = input([int, 3])
    ABC = input([[int, 3], M])

    # Nから到達できる辺のみ抽出する
    g = nlist([N + 1], [])
    for a, b, _ in ABC:
        g[b] += [a]
    que, rch = [N], {N}
    while que:
        cur = que.pop()
        for nxt in g[cur]:
            if nxt in rch: continue
            rch |= {nxt}
            que.append(nxt)
    edges = [(a, b, c) for a, b, c in ABC if a in rch and b in rch]

    # ベルマンフォード法で負の最短経路(スコアの最大値)を導出する
    g = nlist([N + 1], INF)
    g[1] = 0
    for _ in range(N):
        f = True
        for a, b, c in edges:
            c = -(c - P)
            if g[a] + c < g[b]:
                g[b] = g[a] + c
                f = False
        if f:
            break
    else:
        # 負の閉路を除外する
        print(-1)
        return
    print(max(0, -g[N]))
    return

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# from collections import deque
# import numpy as np
import sys
sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


INF = 10**18
N, M, P = _li()

edge_cost = []
edge_from = [[] for _ in range(N)]
edge_to = [[] for _ in range(N)]

for _ in range(M):
    a, b, c = _li()
    a -= 1
    b -= 1
    edge_cost.append((a, b, -(c-P)))
    edge_to[a].append(b)
    edge_from[b].append(a)


ok_from_start = [False] * N
ok_from_end = [False] * N


def reachable_start(node):
    if not ok_from_start[node]:
        ok_from_start[node] = True
        for n in edge_to[node]:
            reachable_start(n)


def reachable_end(node):
    if not ok_from_end[node]:
        ok_from_end[node] = True
        for n in edge_from[node]:
            reachable_end(n)


reachable_start(0)
reachable_end(N-1)
ok = [a and b for a, b in zip(ok_from_start, ok_from_end)]

shortest_path = [INF] * N
shortest_path[0] = 0

# Bellman-Ford
contain_negative_loop = False
for i in range(N):
    update_flag = False
    for ec in edge_cost:
        cand = shortest_path[ec[0]] + ec[2]
        if ok[ec[0]] and ok[ec[1]] and shortest_path[ec[1]] > cand:
            shortest_path[ec[1]] = cand
            update_flag = True
    if not update_flag:
        break

if update_flag:
    contain_negative_loop = True

if contain_negative_loop:
    print(-1)
else:
    print(max(0, -shortest_path[-1]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# from collections import deque
# import numpy as np
import sys
sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N, M, P = _li()

edge_cost = []
edge_from = [[] for _ in range(N)]
edge_to = [[] for _ in range(N)]

for _ in range(M):
    a, b, c = _li()
    a -= 1
    b -= 1
    edge_cost.append((a, b, -(c-P)))
    edge_to[a].append(b)
    edge_from[b].append(a)


# ok_from_start = [False] * N
# ok_from_end = [False] * N


def reachable_start(node):
    if not ok_from_start[node]:
        ok_from_start[node] = True
        for n in edge_to[node]:
            reachable_start(n)


def reachable_end(node):
    if not ok_from_end[node]:
        ok_from_end[node] = True
        for n in edge_from[node]:
            reachable_end(n)


class ReachableSearch(object):
    def __init__(self, result, edge_list):
        self.result = result
        self.edge_list = edge_list

    def search(self, node):
        if not self.result[node]:
            self.result[node] = True
            for n in self.edge_list[node]:
                self.search(n)


# reachable_start(0)
# reachable_end(N-1)
ok_from_start = ReachableSearch([False] * N, edge_to)
ok_from_start.search(0)
ok_from_end = ReachableSearch([False] * N, edge_from)
ok_from_end.search(N-1)


ok = [a and b for a, b in zip(ok_from_start.result, ok_from_end.result)]

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

# Bellman-Ford
contain_negative_loop = False
for i in range(N):
    update_flag = False
    for ec in edge_cost:
        cand = shortest_path[ec[0]] + ec[2]
        if ok[ec[0]] and ok[ec[1]] and shortest_path[ec[1]] > cand:
            shortest_path[ec[1]] = cand
            update_flag = True
    if not update_flag:
        break
if i == N - 1 and update_flag:
    contain_negative_loop = True

if contain_negative_loop:
    print(-1)
else:
    print(max(0, -shortest_path[-1]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# from collections import deque
# import numpy as np
import sys
sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N, M, P = _li()

edge_cost = []
edge_from = [[] for _ in range(N)]
edge_to = [[] for _ in range(N)]

for _ in range(M):
    a, b, c = _li()
    a -= 1
    b -= 1
    edge_cost.append((a, b, -(c-P)))
    edge_to[a].append(b)
    edge_from[b].append(a)


ok_from_start = [False] * N
ok_from_end = [False] * N


def reachable_start(node):
    if not ok_from_start[node]:
        ok_from_start[node] = True
        for n in edge_to[node]:
            reachable_start(n)


def reachable_end(node):
    if not ok_from_end[node]:
        ok_from_end[node] = True
        for n in edge_from[node]:
            reachable_end(n)


reachable_start(0)
reachable_end(N-1)

ok = [a and b for a, b in zip(ok_from_start, ok_from_end)]

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

# Bellman-Ford
contain_negative_loop = False
for i in range(N):
    update_flag = False
    for ec in edge_cost:
        if ok[ec[0]] and ok[ec[1]]:
            if shortest_path[ec[1]] > shortest_path[ec[0]] + ec[2]:
                shortest_path[ec[1]] = shortest_path[ec[0]] + ec[2]
                update_flag = True
    if not update_flag:
        break
if i == N - 1 and update_flag:
    contain_negative_loop = True

if contain_negative_loop:
    print(-1)
else:
    print(max(0, -shortest_path[-1]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    INF = float('inf')
    N, M, P = map(int, input().split())
    dist = [0] + [INF] * (N-1)
    ABC = []
    
    for i in range(M):
        A, B, C = map(int, input().split())
        ABC.append((A-1, B-1, -(C-P)))
        
    for i in range(N):
        for A, B, C in ABC:
            dist[B] = min(dist[B], dist[A]+C)
            
    ans = dist[N-1]
    for i in range(N):
        for A, B, C in ABC:
            dist[B] = min(dist[B], dist[A]+C)
    
    if ans == dist[N-1]:
        print(max(-ans, 0))
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

score = [-float('inf')] * n
score[0] = 0

for i in range(n - 1):
    for a, b, c in abc_list:
        new_score = score[a] + c
        if new_score > score[b]:
            score[b] = new_score
score1 = score[-1]

for i in range(n - 1):
    for a, b, c in abc_list:
        new_score = score[a] + c
        if new_score > score[b]:
            score[b] = new_score
score2 = score[-1]

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

Submission status: Time Limit Exceeded

Solution code:
N, M, P = map(int, input().split())
E = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a - 1, b - 1, P - c)

d = [float("inf") for _ in range(N)]
d[0] = 0
for i in range(2*N):
    for f, t, w in E:
        if d[f] != float("inf") and d[t] > d[f] + w:
            d[t] = d[f] + w
            if i >= N:
                d[t] = -float("inf")
    if i == N-1:
        dN = d[-1]
if dN != d[-1]:
    print(-1)
elif dN > 0:
    print(0)
else:
    print(-dN)

Submission status: Time Limit Exceeded

Solution code:
N, M, P = map(int, input().split())
E = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a - 1, b - 1, P - c)

d = [float("inf") for _ in range(N)]
d[0] = 0
for i in range(N):
    for f, t, w in E:
        if d[f] != float("inf") and d[t] > d[f] + w:
            d[t] = d[f] + w
for i in range(N):
    for f, t, w in E:
        if d[f] != float("inf") and d[t] > d[f] + w:
            d[t] = -float("inf")
if d[-1] == -float("inf"):
    print(-1)
elif d[-1] > 0:
    print(0)
else:
    print(-d[-1])

Submission status: Time Limit Exceeded

Solution code:
N, M, P = map(int, input().split())
E = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a - 1, b - 1, P - c)

d = [float("inf") for _ in range(N)]
d[0] = 0
for i in range(N):
    for (f, t, w) in E:
        if d[f] != float("inf") and d[t] > d[f] + w:
            d[t] = d[f] + w
            if i == N - 1 and t == N - 1:
                print(-1)
                exit()
if d[-1] > 0:
    print(0)
else:
    print(-d[-1])

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
sys.setrecursionlimit(10 ** 5)
N, M, P = map(int, input().split())
e = collections.defaultdict(list)
for _ in range(M):
  u, v, c = map(int, input().split())
  e[u].append((v, c))
def isConnected(n):
  if n == N:
    return True
  vis = [0] * (N + 1)
  que = collections.deque([])
  que.append(n)
  while que:
    nc = que.popleft()
    vis[nc] = 1
    for o in e[nc]:
      if o[0] == N:
        return True
      if vis[o[0]] == 0:
        que.append(o[0])
  return False
inf = 10 ** 10
visited = [0] * (N + 1)
earn = [-inf] * (N + 1)
earn[1] = 0
def dfs(now):
  global visited
  global earn
  visited[now] = 1
  for n in e[now]:
    if visited[n[0]] == 0:
      if n[1] + earn[now] - P > earn[n[0]]:
        earn[n[0]] = n[1] + earn[now] - P
        dfs(n[0])
        visited[n[0]] = 0
    else:
      if earn[n[0]] < n[1] + earn[now] - P:
        if isConnected(n[0]) == True:
          print(-1)
          exit(0)
dfs(1)
print(max(earn[N], 0))