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: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
def bellman_ford(edges, n, src):
    # n:ノード数, src:スタートノード
    # edges:edge(src, tgt, cost)のリスト
    inf = float('inf')
    dist = [inf for _ in range(n)]
    dist[src] = 0
    # 移動経路
    pre = {}

    # 最短経路算出
    for i in range(n-1):
        for edge in edges:
            # srcにコストがあり、tgtのコストよりも低いコストで更新できそうなら
            if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                pre[edge[1]] = edge[0]

    # 負の閉路検出
    def checkpath(pre, n, src):
        if src in pre and pre[n-1] == src and pre[src] == n-1:
            return True
        count = 0
        p = pre[n-1]
        while p != src:
            p = pre[p]
            if p == src and src in pre:
                return True
            count += 1
            if count >= n-1:
                return True
        return False

    is_cycle = checkpath(pre, n, src)
    return (dist, is_cycle)


def dfs(edge, src):
    use = {src}
    q = [src]
    while q:
        v = q.pop()
        for w in edge[v]:
            if w in use:
                continue
            use.add(w)
            q.append(w)
    return use


N, M, P = map(int, input().split())
edges = []
l = [[] for _ in range(N)]
ll = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append([a-1, b-1, -c+P])
    l[a-1].append(b-1)
    ll[b-1].append(a-1)
use = dfs(l, 0) & dfs(ll, N-1)
edges = [(a, b, c) for a, b, c in edges if a in use and b in use]
dist, is_cycle = bellman_ford(edges, N, 0)
if is_cycle:
    print(-1)
else:
    print(max(-dist[N-1], 0))

Submission status: Wrong Answer

Solution code:
def bellman_ford(edges, n, src):
    # n:ノード数, src:スタートノード
    # edges:edge(src, tgt, cost)のリスト
    inf = float('inf')
    dist = [inf for _ in range(n)]
    dist[src] = 0
    # 移動経路
    pre = {}

    # 最短経路算出
    for i in range(n-1):
        for edge in edges:
            # srcにコストがあり、tgtのコストよりも低いコストで更新できそうなら
            if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                pre[edge[1]] = edge[0]

    # 負の閉路検出
    def checkpath(pre, n, src):
        if src in pre and pre[n-1] == src and pre[src] == n-1:
            return True
        count = 0
        p = pre[n-1]
        while p != src:
            p = pre[p]
            if p == src and src in pre:
                return True
            count += 1
            if count >= n-1:
                return True
        return False

    is_cycle = checkpath(pre, n, src)
    return (dist, is_cycle)


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])
dist, is_cycle = bellman_ford(edges, N, 0)
if is_cycle:
    print(-1)
else:
    print(max(-dist[N-1], 0))

Submission status: Wrong Answer

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for _ in range(N-1):
        for u, v, cost in edges:
            if res[v] > res[u] + cost:
                res[v] = res[u] + cost
    tmp = res[:]
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for _ in range(N-1):
        for u, v, cost in edges:
            if res[v] > res[u] + cost:
                # 検出した負閉路はすぐに-INFにする
                res[v] = -INF
    for i in range(N):
        if tmp[i] != res[i]:
            res[i] = -INF
    return res

N, M, P = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, P-c))

res = bellman_ford(N, edges, 0)

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

Submission status: Wrong Answer

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for _ in range(N-1):
        for u, v, cost in edges:
            if res[v] > res[u] + cost:
                res[v] = res[u] + cost
    tmp = res[:]
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for _ in range(N-1):
        for u, v, cost in edges:
            if res[v] > res[u] + cost:
                res[v] = res[u] + cost
    for i in range(N):
        if tmp[i] != res[i]:
            res[i] = -INF
    return res

N, M, P = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, P-c))

res = bellman_ford(N, edges, 0)

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

Submission status: Wrong Answer

Solution code:
inf = float('inf')
N,M,P = map(int,input().split())
edge = []
edge_rev = []
for i in range(M):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,P-c])
    edge_rev.append([b-1,a-1,P-c])
d = [inf]*N
d[0] = 0
for i in range(N):
    update = False
    for j in range(M):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
ans = d[-1]
for i in range(N):
    update = False
    for j in range(M):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
d_rev = [inf]*N
d_rev[N-1] = 0
for i in range(N):
    update = False
    for j in range(M):
        From,To,cost = edge_rev[j]
        if d_rev[From] != inf and d_rev[To]>d_rev[From]+cost:
            d_rev[To]=d_rev[From]+cost
            update = True
    if not update:
        break

loop = False
for i in range(N):
    if ans > d[i]+d_rev[i]:
        loop = True
        break

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

Submission status: Wrong Answer

Solution code:
inf = float('inf')
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,P-c])
d = [inf]*N
d[0] = 0
for i in range(N):
    update = False
    for j in range(M):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
ans = d[-1]
for i in range(N):
    update = False
    for j in range(M):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
if ans > d[-1]:
    ans = -1
else:
    ans = max(-ans,0)
print(ans)

Submission status: Wrong Answer

Solution code:
inf = float('inf')
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,P-c])
d = [inf]*N
d[0] = 0
for i in range(N):
    update = False
    for j in range(M):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
ans = d[-1]
for i in range(N):
    update = False
    for j in range(M):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
if ans < d[-1]:
    ans = -1
else:
    ans = max(-ans,0)
print(ans)

Submission status: Wrong Answer

Solution code:
inf = float('inf')
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,P-c])
d = [inf]*N
d[0] = 0
for i in range(N):
    update = False
    for j in range(M):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
ans = d[-1]
for i in range(N):
    update = False
    for j in range(M):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break
if ans != d[-1]:
    ans = -1
else:
    ans = max(-ans,0)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m,p=[int(j) for j in input().split()]
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
def dfs(edge,s):
    use={s}
    q=[s]
    while q:
        v=q.pop()
        for w in edge[v]:
            if w in use:continue
            use.add(w)
            q.append(w)
    return use


l=[[] for i in range(n)]
ll=[[] for i in range(n)]
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    l[a-1].append(b-1)
    ll[b-1].append(a-1)
    e.append((a-1,b-1,p-c))
use=dfs(l,0)&dfs(ll,n-1)
e=[(a,b,c) for a,b,c in e if (a in use and b in use)]

edge=np.array(e,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2])),(n,n))

while True:
    try:
        #False->無向グラフ True->有効グラフ
        ans=bellman_ford(graph,directed=True,indices=[0])[0].astype(int)
        print(max(0,int(-ans[-1])))
        break
    except:
        #負経路の場合
        print(-1)
        break

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m,p=[int(j) for j in input().split()]

def bellman_ford(v, s, e):
    INF = 10**18
    # コストをINFで初期化
    d =[0] + [INF] * (v-1)
    # 開始頂点は0
    d[s] = 0
    # 負の閉路が無ければ更新はV-1回までで終わる
    for _ in range(v):
        f = False
        for a, b, c in e:
            # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
        # 更新が無ければbreak
        if not f:
            break
    else:
        # V回目まで更新があったら負の閉路がある
        print(-1)
        exit()
    print(max(-d[-1],0))

def dfs(edge,s):
    use={s}
    q=[s]
    while q:
        v=q.pop()
        for w in edge[v]:
            if w in use:continue
            use.add(w)
            q.append(w)
    return use


l=[[] for i in range(n)]
ll=[[] for i in range(n)]
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    l[a-1].append(b-1)
    ll[b-1].append(a-1)
    e.append((a-1,b-1,p-c))
    use=dfs(l,0)&dfs(ll,n-1)
    e=[(a,b,c) for a,b,c in e if (a in use and b in use)]


bellman_ford(n, 0, e)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m,p=[int(j) for j in input().split()]

def bellman_ford(v, s, e):
    INF = 10**18
    # コストをINFで初期化
    d = [INF] * v
    # 開始頂点は0
    d[s] = 0
    # 負の閉路が無ければ更新はV-1回までで終わる
    for _ in range(v):
        f = False
        for a, b, c in e:
            # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
        # 更新が無ければbreak
        if not f:
            break
    else:
        # V回目まで更新があったら負の閉路がある
        print(-1)
        exit()
    print(max(-d[-1],0))

def dfs(edge,s):
    use={s}
    q=[s]
    while q:
        v=q.pop()
        for w in edge[v]:
            if w in use:continue
            use.add(w)
            q.append(w)
    return use


l=[[] for i in range(n)]
ll=[[] for i in range(n)]
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    l[a-1].append(b-1)
    ll[b-1].append(a-1)
    e.append((a-1,b-1,p-c))
    use=dfs(l,0)&dfs(ll,n-1)
    e=[(a,b,c) for a,b,c in e if (a in use and b in use)]


bellman_ford(n, 0, e)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m,p=[int(j) for j in input().split()]
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
def dfs(edge,s):
    use={s}
    q=[s]
    while q:
        v=q.pop()
        for w in edge[v]:
            if w in use:continue
            use.add(w)
            q.append(w)
    return use


l=[[] for i in range(n)]
ll=[[] for i in range(n)]
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    l[a-1].append(b-1)
    ll[b-1].append(a-1)
    e.append((a-1,b-1,p-c))
    use=dfs(l,0)&dfs(ll,n-1)
    e=[(a,b,c) for a,b,c in e if (a in use and b in use)]

edge=np.array(e,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2])),(n,n))

while True:
    try:
        #False->無向グラフ True->有効グラフ
        ans=bellman_ford(graph,directed=True,indices=[0])[0].astype(int)
        print(max(0,int(-ans[-1])))
        break
    except:
        #負経路の場合
        print(-1)
        break

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m,p=[int(j) for j in input().split()]

def bellman_ford(v, s, e):
    INF = 10**18
    # コストをINFで初期化
    d = [INF] * v
    # 開始頂点は0
    d[s] = 0
    # 負の閉路が無ければ更新はV-1回までで終わる
    for _ in range(v):
        f = False
        for a, b, c in e:
            if d[a]==INF:continue
            # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
        # 更新が無ければbreak
        if not f:
            break
    else:
        # V回目まで更新があったら負の閉路がある
        print(-1)
        exit()
    print(max(-d[-1],0))

def dfs(edge,s):
    use={s}
    q=[s]
    while q:
        v=q.pop()
        for w in edge[v]:
            if w in use:continue
            use.add(w)
            q.append(w)
    return use


l=[[] for i in range(n)]
ll=[[] for i in range(n)]
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    l[a-1].append(b-1)
    ll[b-1].append(a-1)
    e.append((a-1,b-1,p-c))
    use=dfs(l,0)&dfs(ll,n-1)
    e=[(a,b,c) for a,b,c in e if (a in use and b in use)]


bellman_ford(n, 0, e)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m,p=[int(j) for j in input().split()]
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
def dfs(edge,s):
    use={s}
    q=[s]
    while q:
        v=q.pop()
        for w in edge[v]:
            if w in use:continue
            use.add(w)
            q.append(w)
    return use


l=[[] for i in range(n)]
ll=[[] for i in range(n)]
e=[]
for i in range(m):
    a,b,c=[int(j) for j in input().split()]
    l[a-1].append(b-1)
    ll[b-1].append(a-1)
    e.append((a-1,b-1,p-c))
    use=dfs(l,0)&dfs(ll,n-1)
    e=[(a,b,c) for a,b,c in e if (a in use and b in use)]

edge=np.array(e,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2])),(n,n))

while True:
    try:
        #False->無向グラフ True->有効グラフ
        ans=bellman_ford(graph,directed=True,indices=0)
        print(max(0,int(-ans[-1])))
        break
    except:
        #負経路の場合
        print(-1)
        break

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def BellmanFord(graph,num_v,source=0):
    # graph = 隣接リスト g[source]=[(destination, dist),...]
    # edgeの初期化 edge = [(source,destination,dist),...]
    edges=[]
    for u in range(num_v):
        for v,d in graph[u]:
            edges.append((u,v,d))
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source]=0
    neg=[False for i in range(num_v)]
    neg_flg=False
    
    #辺の緩和
    for i in range(num_v):
#       負閉路があっても、それを通ってスタートからゴールに辿り着けない場合は結果に影響しない事に注意！
        if i==num_v-1:
            check=dist[n-1]
        for u,v,d in edges:
            if dist[v] > dist[u] + d:
                dist[v] = dist[u] + d
                if i==num_v-1:# and neg[v]==True:
                    # N回目で更新があったという事は負閉路が存在する
                    neg_flg=True
                neg[v] = True
    
    return neg_flg,dist
 

show_flg=False
show_flg=True


n,m,p=MI()
g=[[] for i in range(n)]
for i in range(m):
    a,b,c=LI_()
    c+=1
    #g.append((a-1,b-1,p-c))
    g[a].append((b,p-c))
    
q=[0]
v=[0 for i in range(n)]
v[0]=1
while q:
    c=q.pop()
    for nb,d in g[c]:
        if v[nb]==0:
            v[nb]=1
            q.append(nb)

for i in range(n):
    if v[i]==0:
        g[i]=[]

fl,d=BellmanFord(g,n,0)
ans=d[n-1]

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def BellmanFord(graph,num_v,source=0):
    # graph = 隣接リスト g[source]=[(destination, dist),...]
    # edgeの初期化 edge = [(source,destination,dist),...]
    edges=[]
    for u in range(num_v):
        for v,d in graph[u]:
            edges.append((u,v,d))
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source]=0
    neg=[False for i in range(num_v)]
    neg_flg=False
    
    #辺の緩和
    for i in range(num_v):
#       負閉路があっても、それを通ってスタートからゴールに辿り着けない場合は結果に影響しない事に注意！
        if i==num_v-1:
            check=dist[n-1]
        for u,v,d in edges:
            if dist[v] > dist[u] + d:
                dist[v] = dist[u] + d
                if i==num_v-1:# and neg[v]==True:
                    # N回目で更新があったという事は負閉路が存在する
                    neg_flg=True
                neg[v] = True
    
    if neg_flg:
        for i in range(num_v):
            for u,v,d in edges:
                if dist[v] > dist[u] + d:
                    dist[v] = dist[u] + d
        if dist[n-1]==check:
            neg_flg=False
    return neg_flg,dist
 

show_flg=False
show_flg=True


n,m,p=MI()
g=[[] for i in range(n)]
for i in range(m):
    a,b,c=LI_()
    c+=1
    #g.append((a-1,b-1,p-c))
    g[a].append((b,p-c))
    
q=[0]
v=[0 for i in range(n)]
v[0]=1
while q:
    c=q.pop()
    for nb,d in g[c]:
        if v[nb]==0:
            v[nb]=1
            q.append(nb)

for i in range(n):
    if v[i]==0:
        g[i]=[]

fl,d=BellmanFord(g,n,0)
ans=d[n-1]

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def BellmanFord(graph,num_v,source=0):
    # graph = 隣接リスト g[source]=[(destination, dist),...]
    # edgeの初期化 edge = [(source,destination,dist),...]
    edges=[]
    for u in range(num_v):
        for v,d in graph[u]:
            edges.append((u,v,d))
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source]=0
    neg=[False for i in range(num_v)]
    neg_flg=False
    
    #辺の緩和
    for i in range(num_v):
#       負閉路があっても、それを通ってスタートからゴールに辿り着けない場合は結果に影響しない事に注意！
        if i==num_v-1:
            check=dist[n-1]
        for u,v,d in edges:
            if dist[v] > dist[u] + d:
                dist[v] = dist[u] + d
                if i==num_v-1:# and neg[v]==True:
                    # N回目で更新があったという事は負閉路が存在する
                    neg_flg=True
                neg[v] = True
    
    if neg_flg:
        for i in range(num_v):
            for u,v,d in edges:
                if dist[v] > dist[u] + d:
                    dist[v] = dist[u] + d
        if dist[n-1]==check:
            neg_flg=False
    return neg_flg,dist
 

show_flg=False
show_flg=True


n,m,p=MI()
g=[[] for i in range(n)]
for i in range(m):
    a,b,c=LI_()
    c+=1
    #g.append((a-1,b-1,p-c))
    g[a].append((b,p-c))
    

fl,d=BellmanFord(g,n,0)
ans=d[n-1]

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def BellmanFord(graph,num_v,source=0):
    # graph = 隣接リスト g[source]=[(destination, dist),...]
    # edgeの初期化 edge = [(source,destination,dist),...]
    edges=[]
    for u in range(num_v):
        for v,d in graph[u]:
            edges.append((u,v,d))
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source]=0
    neg=[False for i in range(num_v)]
    neg_flg=False
    
    #辺の緩和
    for i in range(num_v):
#       負閉路があっても、それを通ってスタートからゴールに辿り着けない場合は結果に影響しない事に注意！
        if i==num_v-1:
            check=dist[n-1]
        for u,v,d in edges:
            if dist[v] > dist[u] + d:
                dist[v] = dist[u] + d
                if i==num_v-1:# and neg[v]==True:
                    # N回目で更新があったという事は負閉路が存在する
                    neg_flg=True
                neg[v] = True
    
    if neg_flg:
        for u,v,d in edges:
            if dist[v] > dist[u] + d:
                dist[v] = dist[u] + d
        if dist[n-1]==check:
            neg_flg=False
    return neg_flg,dist
 

show_flg=False
show_flg=True


n,m,p=MI()
g=[[] for i in range(n)]
for i in range(m):
    a,b,c=LI_()
    c+=1
    #g.append((a-1,b-1,p-c))
    g[a].append((b,p-c))
    

fl,d=BellmanFord(g,n,0)
ans=d[n-1]

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