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:
N, M, P = map(int, input().split())
E = [[] for _ in range(M)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[i] = [a - 1, b - 1, c]
D = [None] * N
D[0] = 0
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
_D = D[-1]
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
if D[-1] > _D:
  print(-1)
else:
  print(max(D[-1], 0))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Solution code:
import sys
def main():
    N, M, P = map(int, input().split())
    Edge = []
    for i in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        a, b = a - 1, b - 1
        c = -(c - P)
        Edge.append([a, b, c])

    # ベルマンフォード
    dist = [float('inf')] * N
    dist[0] = 0

    for i in range(2 * N):
        for fr, to, cost in Edge:
            if (dist[fr] != float('inf')) and (dist[to] > dist[fr] + cost):
                dist[to] = dist[fr] + cost
                if (i >= N) & (to == N - 1):
                    print(-1)
                    exit()

    print(max(0, -dist[N - 1]) if -dist[N - 1] != float('inf') else 0)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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 _ 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
		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(max(-bf.GetDistance(n-1), 0))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M, P = map(int, input().split())
    Edge = []
    for i in range(M):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        c = -(c - P)
        Edge.append([a, b, c])

    # ベルマンフォード
    dist = [float('inf')] * N
    dist[0] = 0

    for i in range(2 * N):
        for fr, to, cost in Edge:
            if (dist[fr] != float('inf')) and (dist[to] > dist[fr] + cost):
                dist[to] = dist[fr] + cost
                if (i >= N) & (to == N - 1):
                    print(-1)
                    exit()

    print(max(0, -dist[N - 1]) if -dist[N - 1] != float('inf') else 0)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

        prev = total_cost
        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:
                        break
                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

            if total_cost == prev:
                return total_cost
            prev = total_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: Time Limit Exceeded

Solution code:
import sys
n, m, p = [int(i) for i in sys.stdin.readline().split()]
d = [0 for i in range(n)]
edge_ls = []
prev = [-1 for i in range(n)]
INF = 1e18
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    edge_ls.append([a-1,b-1,p-c])

def find_negative_loop():
    for i in range(n):
        for j in range(m):
            e = edge_ls[j]
            if d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                if i == n - 1:
                    return True
    return False

def shortest_path(s):
    for i in range(n):
        d[i] = INF
    d[s] = 0
    cnt = 0
    while True:
        update = False
        for i in range(m):
            e = edge_ls[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]
            cnt += 1
            if cnt > (n - 1) * m:
                break
        if not update:
            break

def _find_negative_loop():
    for i in range(n):
        for j in range(m):
            e = edge_ls[j]
            if d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                if i == n - 1 and root.get(e[0]) == e[1]:
                    return True
    return False

shortest_path(0)
cand = -min(0, d[n-1])
now = n-1
root = {}
cnt = 0
while True:
    _next = prev[now]
    root[_next] = now
    now = _next
    if now == 0:
        break
    cnt += 1
    if cnt > n:
        break
if _find_negative_loop():
    print("-1")
else:
    if cand == -INF:
        print(0)
    else:
        print(cand)

Submission status: Time Limit Exceeded

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

Solution code:
n, m, p = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]

for i in range(m):
    A[i][2] = - (A[i][2]-p)


import numpy as np
S = [np.inf for i in range(n+1)]

S[1]=0
for i in range(m):
    if A[i][0] == 1:
        S[A[i][1]]=A[i][2]

for j in range(n-1):
    for i in range(m):
        S[A[i][1]] = min(S[A[i][1]], S[A[i][0]]+A[i][2])

#print(S)
ans1 = -S[n]

for j in range(1):
    for i in range(m):
        S[A[i][1]] = min(S[A[i][1]], S[A[i][0]]+A[i][2])
#print(S)
ans2 = -S[n]

if ans1 != ans2:
    print(-1)
else:
    print(max(0, ans1))

Submission status: Time Limit Exceeded

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

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


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

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

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

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




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


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

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

            else:
                ans = d[N]

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


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

scoren = score.copy()

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

Submission status: Time Limit Exceeded

Solution code:

N, M,P = list(map(int, input().split()))
ABC = [tuple(map(int, input().split())) for _ in range(M)]
#ABCp = [(a,b,c-P) for a,b,c in ABC]


_d = {i:[] for i in range(N+1)}
for a,b,c in ABC:
  _d[b].append((a,c-P))
  
#print(_d)

INF = 10**9

#始点から頂点への最長経路 D[1]:始点, D[N]:終点
D = [-INF]*(N+1)
D[1] = 0
#print(D)


# N-1会の繰り返し
for _ in range(N-1):
  D = [max([D[a]+c for a,c in _d[b]]+[D[b]]) for b in range(N+1)]
  #print(D)
  
ans = D[N]
for _ in range(N):
  D = [max([D[a]+c for a,c in _d[b]]+[D[b]]) for b in range(N+1)]
  
if ans != D[N]:
  print(-1)
else:
  print(max(0,ans))

Submission status: Time Limit Exceeded

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

def main():
    N, M, P = map(int, input().split())
    g = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]
    data = [list(map(int, input().split())) for _ in range(M)]


    for a, b, _ in data:
        g[b].append(a)
        g2[a].append(b)

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

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

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




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


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

    for i in range(N):
        d_N = [d[i] for i in range(1, N+1) if visit[i]]
        for j in range(M):

            d[data[j][1]] = max(d[data[j][1]], d[data[j][0]]+data[j][2]-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
from array import array


def solve(N, M, P, A, B, C):
    INF = 10 ** 12

    edges = []
    for a, b, c in zip(A, B, C):
        edges.append((a, b, P - c))

    prev = array("i", [0] * (1 + N))
    cost = array("q", [INF] * (1 + N))
    cost[1] = 0

    infloop = True
    for _ in range(N):
        update = False
        for a, b, c in edges:
            if cost[a] != INF and cost[b] > cost[a] + c:
                update = True
                cost[b] = cost[a] + c
                prev[b] = a
        if not update:
            infloop = False
            break

    if infloop:
        v = N
        goaled = 0
        for _ in range(2 * N):
            v = prev[v]
            if v == 1:
                goaled += 1
        if goaled != 1:
            return -1

    return max(0, -cost[N])


# -----------------------------------------------------------------------------
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))

    ans = solve(N, M, P, A, B, C)
    if ans is not None:
        print(ans)


if __name__ == '__main__':
    main()