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:
from collections import defaultdict, deque

N, M, P = map(int, input().split())
G = defaultdict(lambda: defaultdict(lambda: 0))
G_rev = defaultdict(lambda: defaultdict(lambda: 0))

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

reachable = [0] * (N + 1)
reachable[N] = 1
queue = deque([N])

while len(queue) > 0:
    p = queue.popleft()
    for q in G_rev[p].keys():
        if reachable[q] == 0:
            reachable[q] = 1
            queue.append(q)

# print(reachable)
assert reachable[1] == 1

dist = [10000000000] * (N + 1)
res = 0
dist[1] = 0
queue = deque([1])
cnt = 0
while len(queue) > 0:
    p = queue.popleft()
    for q in G[p].keys():
        if reachable[q] == 0:
            pass
        elif dist[p] + G[p][q] < dist[q]:
            dist[q] = dist[p] + G[p][q]
            queue.append(q)
            cnt += 1
    if cnt > 100000:
        res = -1
        break

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

Submission status: Wrong Answer

Solution code:
import sys
N,M,p=map(int,input().split())
edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    edge.append([a-1,b-1,-c+p])
inf=10**30
ct=0
dist=[inf]*N
dist[0]=0
for i in range(N+1):
    for x,y,z in edge:
        if dist[y]<= dist[x]+z:
            ct+=1
            continue
        dist[y]=dist[x]+z
        if i==N and y==N-1:
            print('-1')
            sys.exit()
print(max(-dist[N-1],0))

Submission status: Wrong Answer

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

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

    INF = 10**27
    V = [INF]*N
    V[0] = 0
    for _ in range(N-1):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    ans = V[N-1]
    for _ in range(N):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]

    if V[N-1] < ans:
        print(-1)
        return
    print( max(-ans,0))
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


# 有効グラフを仮定する。
class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    visited = [False]*g.N

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        if visited[u] == False:
            visited[u] = True

        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                if visited[v] == True:
                    dist[v] = -INF
                else:
                    dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))

    return dist, prev


def solve(N: int, M: int, P: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    for i in range(M):
        C[i] = P - C[i]

    g = Graph(N)
    for a, b, c in zip(A, B, C):
        g.add_edge([a-1, b-1, c])

    dist, prev = shortestPath(g, 0)
    if -dist[-1] == INF:
        print(-1)
    else:
        print(max(-dist[-1], 0))

    # print(longest)
    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: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n, m, p = li()
edges = []
for _ in range(m):
    ai, bi, ci = li()
    ai -= 1
    bi -= 1
    edges.append((ai, bi, ci-p))

INF = 10**12
dist = [[-INF]*n for _ in range(2*n+1)]
dist[0][0] = 0

for i in range(2*n):
    for j in range(n):
        dist[i+1][j] = dist[i][j]

    for ai, bi, ci in edges:
        dist[i+1][bi] = max(dist[i+1][bi], dist[i][ai] + ci)

if dist[2*n-1][-1] < dist[2*n][-1]:
    print(-1)
else:
    print(max(0, dist[2*n-1][-1]))

Submission status: Wrong Answer

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

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

    INF = 10**15
    V = [INF]*N
    V[0] = 0
    for _ in range(N-1):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    ans = V[N-1]
    for _ in range(N):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]

    if V[N-1] != ans:
        print(-1)
        return
    print( max(-ans,0))
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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 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
		else:
			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(-bf.GetDistance(n-1))

Submission status: Wrong Answer

Solution code:
INF = 10**18
n, m, p = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for i in range(m):
    a, b, c = [int(item) for item in input().split()]
    a -= 1; b -= 1; c -= p
    c *= -1
    edge[a].append((b, c))
 
dist = [INF] * n
dist[0] = 0
update = 1
terminal_update = 0
for _ in range(n):
    update = 0
    for v, e in enumerate(edge):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
                if t == n-1:
                    terminal_update += 1
    if not update:
        print(max(0, -dist[n-1]))
        exit()
else:
    if terminal_update > 1:
        print(-1)
    else:
        print(max(0, -dist[n-1]))

Submission status: Wrong Answer

Solution code:
#https://qiita.com/chun1182/items/ddf2b6cba932b2bb0d4e
def BF(p,n,s):
    inf=float("inf")
    d=[inf for i in range(n)]
    d[s-1]=0
    for i in range(2*n+1):
        for e in p:
            if e[0]!=inf and d[e[1]-1]>d[e[0]-1]+e[2]:
                d[e[1]-1] = d[e[0]-1] + e[2]
        if i==2*n-1:t=d[-1]
        if i==2*n and t!=d[-1]:
            return [0,'inf']
    return list(map(lambda x:-x, d))

n,m,p=map(int,input().split())
g=[]
for _ in range(m):
  a,b,c=map(int,input().split())
  g.append([a,b,-(c-p)])
g.append([n,n+1,0])
ans=BF(g,n+1,1)[-1]
if ans=='inf':
  print(-1)
else:
  print(max(ans,0))

Submission status: Wrong Answer

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

inf = float('inf')

def solve(N: int, M: int, P: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    dist = [inf] * N
    dist[0] = 0
    loop = [False] * N

    for count in range(N):
        for u, v, c in zip(A, B, C):
            n = dist[u] + c
            if n < dist[v]:
                dist[v] = n
                if count >= N:
                    loop[v] = True
    
    if loop[N-1]:
        print(-1)
        return
    print(max(-dist[N-1], 0))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))-1
        B[i] = int(next(tokens))-1
        C[i] = -(int(next(tokens))-P)
    solve(N, M, P, A, B, C)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m, p = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]
score = {}
abc = sorted(abc, key=lambda x: x[1])[::-1]

for a, b, c in abc:
  score_a = score.get(a) or 0
  score_b = score.get(b) or 0
  s = c - p
  if a == b:
    s = float('inf')
  s = max(score_a, score_b + s)
  score[a] = s

  # print(a, b, c, s, score_b)
for k, v in score.items():
  # print(k, v)
  if v == float('inf'):
    score[k] = -1
print(score[1])

Submission status: Wrong Answer

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

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

    INF = 10**15
    V = [INF]*N
    V[0] = 0
    for _ in range(N):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    ans = V[N-1]
    for _ in range(N):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]

    if V[N-1] < ans:
        print(-1)
        return
    print( max(-ans,0))
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
# N = int(input()) #頂点の数
# M = int(input()) #辺の数
N, M, P = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -(s-P)]] #有向グラフのときはここだけ
    # G += [[r-1, l-1, s]] #無向グラフのときはこの行も必要


#メイン文
d = [0] * N #最短距離を記録しておくリスト
# prev = [-1] * N
def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while True:
        count += 1
        update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
                # prev[e[1]] = e[0]
        if not update: #更新が終わったとき
            return True
        if count == N - 1: #永遠に更新が起きているとき
            tmp = d[N -1]
        if count == N:
            if d[N - 1] == tmp:
                return True #N-1の値が更新されていないとき
            else:
                return False #N + 2回目でもN - 1の値が小さくなっている-->得点が無限に大きくなる

#呼び出しスタート地点を入れる
if not shortest_path(1):
    print (-1)
    # print (d)
    exit()
# print (d)

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

Submission status: Wrong Answer

Solution code:
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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


class Dinic:
    def __init__(self, graph=None, residual=None):
        """
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :param list of (list of (list of (int|list))) residual: (to, cap, rev) の残余グラフ
        """
        assert (graph and not residual) or (not graph and residual)
        if graph:
            self.graph = self.residual_graph(graph)
        else:
            self.graph = residual

    @staticmethod
    def residual_graph(graph):
        """
        残余グラフ構築
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :rtype: list of (list of (list of (int|list)))
        :return: (to, cap, rev) の残余グラフ
        """
        ret = [[] for _ in range(len(graph))]
        for v in range(len(graph)):
            for u, cap in graph[v]:
                rev = [v, 0]
                edge = [u, cap, rev]
                rev.append(edge)
                ret[v].append(edge)
                ret[u].append(rev)
        return ret

    def _dist(self, s):
        """
        :param int s:
        :rtype: list of int
        :return: s からの距離。残余グラフ上で到達できない場合は -1
        """
        ret = [-1] * len(self.graph)
        ret[s] = 0
        que = deque([(s, 0)])
        while que:
            v, d = que.popleft()
            for u, cap, _ in self.graph[v]:
                if ret[u] < 0 < cap:
                    ret[u] = d + 1
                    que.append((u, d + 1))
        return ret

    def _dfs(self, s, t, dist, iter, flow=float('inf')):
        """
        :param int s:
        :param int t:
        :param list of int dist:
        :param list of int iter:
        :param int flow:
        """
        if s == t:
            return flow
        while iter[s] < len(self.graph[s]):
            edge = self.graph[s][iter[s]]
            to, cap, rev = edge
            if dist[s] < dist[to] and cap > 0:
                f = self._dfs(to, t, dist, iter, min(flow, cap))
                if f > 0:
                    edge[1] -= f
                    rev[1] += f
                    return f
            iter[s] += 1
        return 0

    def maximum_flow(self, from_v, to_v):
        """
        :param int from_v:
        :param int to_v:
        :return: from_v から to_v への最大流
        """
        ret = 0
        while True:
            dist = self._dist(from_v)
            if dist[to_v] < 0:
                break
            iter = [0] * len(self.graph)
            while True:
                flow = self._dfs(from_v, to_v, dist, iter)
                if flow == 0:
                    break
                ret += flow
        return ret


class MinCostFlow:
    """
    最小費用流 ベルマンフォード版
    """

    def __init__(self, graph=None, residual=None):
        """
        :param list of (list of (int, int, int)) graph: (to, cap, cost) の隣接リスト
        :param list of (list of (list of (int|list))) residual: (to, cap, cost, rev) の残余グラフ
        """
        assert (graph and not residual) or (not graph and residual)
        if graph:
            self.graph = self.residual_graph(graph)
        else:
            self.graph = residual

    @staticmethod
    def residual_graph(graph):
        """
        残余グラフ構築
        :param list of (list of (int, int, int)) graph: (to, cap, cost) の隣接リスト
        :rtype: list of (list of (list of (int|list)))
        :return: (to, cap, cost, rev) の残余グラフ
        """
        ret = [[] for _ in range(len(graph))]
        for v in range(len(graph)):
            for u, cap, cost in graph[v]:
                rev = [v, 0, -cost]
                edge = [u, cap, cost, rev]
                rev.append(edge)
                ret[v].append(edge)
                ret[u].append(rev)
        return ret

    def solve(self, from_v, to_v, flow):
        """
        :param int from_v:
        :param int to_v:
        :param int flow:
        :rtype: int
        """
        remains = flow
        total_cost = 0

        while remains > 0:
            # 最短路
            dist = [float('inf')] * len(self.graph)
            preve = [None] * len(self.graph)
            prevv = [None] * len(self.graph)
            dist[from_v] = 0
            stop = False
            cnt = 0
            while not stop:
                stop = True
                for v, edges in enumerate(self.graph):
                    for edge in edges:
                        u, cap, cost, rev = edge
                        if cap > 0 and dist[v] + cost < dist[u]:
                            dist[u] = dist[v] + cost
                            prevv[u] = v
                            preve[u] = edge
                            stop = False
                cnt += 1
                if cnt > len(self.graph) + 100:
                    if prevdist != dist[to_v]:
                        return IINF
                    else:
                        return total_cost
                prevdist = dist[to_v]
            flow = remains
            if dist[to_v] == float('inf'):
                total_cost = -1
                break

            v = to_v
            while v != from_v:
                cap = preve[v][1]
                v = prevv[v]
                flow = min(cap, flow)

            # path に沿って flow 流す
            cost = 0
            v = to_v
            while v != from_v:
                cost += preve[v][2] * flow
                preve[v][1] -= flow
                preve[v][3][1] += flow
                v = prevv[v]

            remains -= flow
            total_cost += cost
        return total_cost


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

S = 0
T = N + 1
graph = [[] for _ in range(N + 2)]
graph[S].append((1, 1, 0))
graph[N].append((T, 1, 0))
for a, b, c in ABC:
    graph[a].append((b, IINF, -c + P))

ans = MinCostFlow(graph).solve(S, T, 1)
if ans == IINF:
    print(-1)
elif ans > 0:
    print(0)
else:

    print(-ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, M: int, P: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    p = [[] for _ in range(N)]
    p_rev = [[] for _ in range(N)]
    for i in range(M):
        p[A[i] - 1].append([B[i] - 1, C[i] - P, i])
        p_rev[B[i] - 1].append([A[i] - 1, C[i] - P, i])

    def detect(idx, cur, start, visited, cnt = 0):
        #print(idx, cur, start, visited)
        if cnt > 0 and idx == start:
            if cur > 0:
                return True
            else:
                return False
        for nex in p[idx]:
            if not visited[nex[0]]:
                visited[nex[0]] = True
                tmp = detect(nex[0], cur + nex[1], start, visited, cnt + 1)
                if tmp:
                    return True
                visited[nex[0]] = False
        return False

    def can1(idx, visited):
        visited[idx] = True
        for nex in p[idx]:
            if not visited[nex[0]]:
                visited = can1(nex[0], visited)
        return visited

    def can2(idx, visited):
        visited[idx] = True
        for nex in p_rev[idx]:
            if not visited[nex[0]]:
                visited = can2(nex[0], visited)
        return visited

    def dfs(idx, cur, dp, used):
        dp[idx] = max(dp[idx], cur)
        for nex in p[idx]:
            if not used[nex[2]]:
                used[nex[2]] = True
                dp = dfs(nex[0], cur + nex[1], dp, used)
        return dp

    visited = [False] * N
    visited_s = can1(0, visited)
    visited = [False] * N
    visited_t = can2(N - 1, visited)
    for i in range(N):
        visited = [False] * N
        tmp = detect(i, 0, i, visited)
        if tmp and visited_s[i] and visited_t[i]:
            #print(i, visited)
            print(-1)
            return

    used = [False] * M
    dp = [0] * N
    dp = dfs(0, 0, dp, used)
    #print(dp)
    ret = max(0, dp[N - 1])
    print(ret)
    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: Wrong Answer

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

inf = float('inf')

def solve(N: int, M: int, P: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    dist = [inf] * N
    dist[0] = 0
    loop = [False] * N

    for count in range(N+N):
        for u, v, c in zip(A, B, C):
            if dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                if count >= v-1:
                    loop[v] = True
    
    if loop[N-1]:
        print(-1)
        return
    print(max(-dist[N-1], 0))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))-1
        B[i] = int(next(tokens))-1
        C[i] = -(int(next(tokens))-P)
    solve(N, M, P, A, B, C)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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


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

    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]
                parent[edge[1]] = edge[0]

    end1 = dist[end]
    trace1 = []
    r = end
    for n in range(num_v):
        trace1.append(r)
        r = parent[r]
        if r == -1:
            break

    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]
                parent[edge[1]] = edge[0]

    end2 = dist[end]
    trace2 = []
    r = end
    for n in range(num_v + 10):
        trace2.append(r)
        r = parent[r]
        if r == -1:
            break

    if trace2[-1] != source:
        return -1

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


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

Submission status: Wrong Answer

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

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

queue = [0]
coins2 = [None] * N
coins2[0] = 0
while queue:
	cur = queue.pop()
	coin = coins2[cur]
#	print(cur, coin)
	for n, c in v_list[cur]:
		x = coins2[n]
		y = coin + c - P
		if x == None:
			coins2[n] = y
			queue.append(n)

queue = [N - 1]
coins = [None] * N
coins[N - 1] = 0
while queue:
	cur = queue.pop()
#	print(">", cur)
	coin = coins[cur]
	for n, c in r_list[cur]:
#		print("<", n)
		x = coins[n]
		y = coin + c - P
		if x == None:
			coins[n] = y
			queue.append(n)
		elif x < y:
			if coins2[n] != None:
#				print(cur, n ,coins, x, y)
				print("-1")
				exit(0)

#print(coins)
#print(coins2)

max_value = 0
for i in range(N):
	coin1 = coins[i]
	coin2 = coins2[i]
	if coin1 != None and coin2 != None:
		coin = coin1 + coin2
		if coin > max_value:
			max_value = coin
print(max_value)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import heapq

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

    gain = [[-10 ** 20, False] for i in range(N)]
    q = deque()
    q.append((0, 0, 0)) #node, gain, roop
    while q:
        now, ng, roop = q.popleft()
        if gain[now][0] == -10 ** 20:
            gain[now][0] = ng
            for next, money in graph[now]:
                q.append((next, ng + money, roop + 1))
        else:
            if roop < N:
                gain[now][0] = max(ng, gain[now][0])
                for next, money in graph[now]:
                    q.append((next, ng + money, roop + 1))
            else:
                if ng > gain[now][0]: gain[now][1] = True
                else: gain[now][1] = False
        #print(graph)
        #print(gain)
    if gain[N-1][1]: print(-1)
    else: print(max(0, gain[N-1][0]))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

graph = {i:[] for i in range(1,N+1)}

d = [[-10**5] * (N+1) for i in [0]*(N+1)]
for i in [0]*M:
	a,b,c = map(int,input().split(' '))
	d[a][b] = c - P

for k in range(1,N+1):
	for i in range(1,N+1):
		for j in range(1,N+1):
			d[i][j] = max(d[i][j], d[i][k] + d[k][j])

for i in range(1,N+1):
	if d[i][i] > 0:
		print(-1)
		exit()

print(d[1][N])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque

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

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

res = [0, 0] + [float("-inf")] * (n - 1)

q = deque()
q.append((1, [0, 0] + [float("-inf")] * (n - 1)))

while q:
    curr, score = q.pop()
    for b, c in edge[curr]:
        if score[b] != float("-inf"):
            if score[curr] + c > score[b]:
                score[curr] = float("inf")
                res[curr] = float("inf")

                for bb, cc in edge[curr]:
                    if score[bb] != float("inf"):
                        score[bb] = float("inf")
                        res[bb] = float("inf")
                        q.append((bb, score))

        else:
            score[b] = score[curr] + c
            if score[b] > res[b]:
                res[b] = score[b]
                q.append((b, score))


print(max(0, res[n]) if res[n] != float("inf") else -1)

Submission status: Wrong Answer

Solution code:
INF = 10**18
n, m, p = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for i in range(m):
    a, b, c = [int(item) for item in input().split()]
    a -= 1; b -= 1; c -= p
    c *= -1
    edge[a].append((b, c))

dist = [INF] * n
dist[0] = 0
update = 1
terminal_update = 0
for _ in range(n + 10):
    update = 0
    for v, e in enumerate(edge):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
                if t == n-1:
                    terminal_update += 1
    if not update:
        print(max(0, -dist[n-1]))
        exit()
else:
    if terminal_update > 1:
        print(-1)
    else:
        print(max(0, -dist[n-1]))