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: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline

n, m, p = map(int, input().split())
graph = [[] for _ in range(n + 1)]
revgraph = [[] for _ in range(n + 1)]
loop = [False] * (n + 1)
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, c - p))
    graph[a].append((b, c - p))
    revgraph[b].append((a, c - p))
is_route = [False] * (n + 1)
# DFS
start = 1

stack = [start]
while stack:
    v = stack.pop()
    is_route[v] = True
    for u, c in graph[v]:
        if is_route[u]:
            continue
        stack.append(u)
is_revroute = [False] * (n + 1)

goal = n
stack = [goal]
while stack:
    v = stack.pop()
    is_revroute[v] = True
    for u, c in revgraph[v]:
        if is_revroute[u]:
            continue
        stack.append(u)


def check(v):
    return is_route[v] and is_revroute[v]


# Bellman-Ford

dist = [-(10 ** 10)] * (n + 1)
start = 1
dist[start] = 0
cnt = 0
update = True
used = set([start])
while update:
    cnt += 1
    update = False
    for fr, to, co in edges:
        if check(fr) and check(to):
            if dist[fr] != -(10 ** 10) and dist[to] < dist[fr] + co:
                dist[to] = dist[fr] + co
                update = True
    if not update:
        break
    if cnt > n:
        print(-1)
        exit()
print(max(0, dist[n]) if dist[n] != -(10 ** 10) else -1)

Submission status: Accepted

Solution code:
import collections
import heapq
import copy
n,m,p = map(int,raw_input().split(' '))

adj = collections.defaultdict(list)
def f(e,p):
	u,v,w = e
	return (u,v,p-w)

edges = [f(map(int, raw_input().split()), p) for _ in range(m) ]

fa = collections.defaultdict(list)
ba = collections.defaultdict(list)
for u,v,_ in edges:
	fa[u].append(v)
	ba[v].append(u)
def dfs(u,adj,vis):
	stack = collections.deque([u])
	while(stack):
		uu = stack.pop()
		vis.add(uu)

		for v in adj[uu]:
			if v not in vis:
				vis.add(v)
				stack.append(v)
va = set([1])
dfs(1, fa, va)

vb = set([n])
dfs(n, ba, vb)

h = {u: (+float('inf') if u > 1 else 0) for u in range(1, n + 1)}

for _ in range(n-1):
	for u,v,w in edges: h[v] = min(h[v], h[u] + w)

fnc = False
for u,v,w in edges: 
	if v in va and v in vb and h[v] > h[u] + w:
		fnc = True
		break
print max(0,-h[n]) if (not(fnc) and h[n] != +float('inf')) else -1

Submission status: Accepted

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

INF = 10**18

N, M, P = map(int, input().split())
G = []
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G.append((a, b, c-P))
D = [0]*N
for i in range(N):
    D[i] = -INF
D[0] = 0
for i in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
updated = [False]*N
for _ in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if (D[fr] != -INF and D[fr]+cost > D[to]) or updated[fr]:
            updated[to] = True
if updated[N-1]:
    print(-1)
elif D[N-1] < 0:
    print(0)
else:
    print(D[N-1])

Submission status: Accepted

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

INF = 10**18

N, M, P = map(int, input().split())
G = []
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G.append((a, b, c-P))
D = [0]*N
for i in range(N):
    D[i] = -INF
D[0] = 0
for i in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
for _ in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = INF
            if to == N-1:
                print(-1)
                exit()
if D[N-1] < 0:
    print(0)
else:
    print(D[N-1])

Submission status: Accepted

Solution code:
INF = 10**18

N, M, P = map(int, input().split())
G = []
G1 = [[] for i in range(N)]
G2 = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G.append((a, b, c-P))
D = [0]*N
for i in range(N):
    D[i] = -INF
D[0] = 0
for i in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
tmpAns = D[N-1]
for _ in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = INF
            if to == N-1 and D[to] != tmpAns:
                print(-1)
                exit()
if D[N-1] < 0:
    print(0)
else:
    print(D[N-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**18

def dfs1(cur):
    for to in G1[cur]:
        if done1[to]: continue
        done1[to] = True
        dfs1(to)

def dfs2(cur):
    for to in G2[cur]:
        if done2[to]: continue
        done2[to] = True
        dfs2(to)

N, M, P = map(int, input().split())
G = []
G1 = [[] for i in range(N)]
G2 = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G.append((a, b, c-P))
    G1[a].append(b)
    G2[b].append(a)
D = [0]*N
for i in range(N):
    D[i] = -INF
D[0] = 0
for i in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
done1 = [False]*N
done1[0] = True
dfs1(0)
done2 = [False]*N
done2[N-1] = True
dfs2(N-1)
for _ in range(N):
    for j in range(M):
        fr, to, cost = G[j]
        if D[fr] != -INF and D[fr]+cost > D[to]:
            D[to] = D[fr]+cost
            if done1[to] and done2[to]:
                print(-1)
                exit()
if D[N-1] < 0:
    print(0)
else:
    print(D[N-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


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


def read_float():
    return float(buff_readline())


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


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


def read_str_n():
    return readline().strip().split()


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


def mt(f):
    import time

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

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

    return wrap


from collections import defaultdict

def BellmanFord(g, s, N):
    dist = [INF] * (N+1)
    dist[s] = 0
    for i in range(N):
        for u in range(1, N+1):
            if dist[u] == INF:
                continue
            for v in g[u]:
                if dist[v] > dist[u] + g[u][v]:
                    dist[v] = dist[u] + g[u][v]
    for i in range(N//2):
        for u in range(1, N+1):
            if dist[u] == INF:
                continue
            for v in g[u]:
                if dist[v] > dist[u] + g[u][v]:
                    if dist[v] != INF:
                        dist[v] = -INF
    return dist


@mt
def slv(N, M, P, ABC):
    g = defaultdict(dict)
    for a, b, c in ABC:
        if a in g and b in g[a]:
            g[a][b] = min(g[a][b], -(c - P))
        else:
            g[a][b] = -(c - P)

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





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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    start = time.time()
    n,m,p = LI()
    abc = [LI() for _ in range(m)]
    er = collections.defaultdict(set)
    err = collections.defaultdict(set)
    for a,b,c in abc:
        er[b].add(a)
        err[a].add(b)

    v = set([n])
    q = [n]
    qi = 0
    while len(q) > qi:
        t = q[qi]
        qi += 1
        for b in er[t]:
            if b not in v:
                v.add(b)
                q.append(b)

    u = set([1])
    q = [1]
    qi = 0
    while len(q) > qi:
        t = q[qi]
        qi += 1
        for b in err[t]:
            if b not in u:
                u.add(b)
                q.append(b)

    v &= u

    e = collections.defaultdict(list)
    for a,b,c in abc:
        if a not in v or b not in v:
            continue
        e[a].append((b,c-p))

    en = len(e)
    km = sum(map(lambda x: x[2], abc))
    def search(s):
        d = collections.defaultdict(lambda: -inf)
        vc = collections.defaultdict(int)
        q = []
        d[s] = 0
        heapq.heappush(q, (0, s))
        ttt = 0
        while len(q):
            ttt += 1
            if ttt % 1024 == 0:
                if time.time() - start > 1.5:
                    return
            mk, u = heapq.heappop(q)
            k = -mk
            if d[u] > k:
                continue
            if k > km or vc[u] > en:
                return
            vc[u] += 1

            for uv, ud in e[u]:
                vd = k + ud
                if d[uv] < vd:
                    d[uv] = vd
                    heapq.heappush(q, (-vd, uv))

        return d

    d = search(1)
    if d is None:
        return -1
    return max(0, d[n])

print(main())

Submission status: Accepted

Solution code:
def bellman_ford(s, n, G):
    d = [float('inf')]*n
    d[s] = 0
    for i in range(n):
        update = False
        for x, y, z in G:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        if i == n - 1:
            return None
    return d

def main():
    n, m, p = map(int, input().split())
    G = []
    U = [[] for _ in range(n)]
    V = [[] for _ in range(n)]
    dic = {}
    for _ in range(m):
        a, b, c = map(int, input().split())
        if (a-1, b-1) in dic:
            if dic[(a-1, b-1)] > -c+p:
                dic[(a-1, b-1)] = -c+p
        else:
            dic[(a-1, b-1)] = -c+p
    for v in dic.keys():
        G.append([v[0], v[1], dic[v]])
        U[v[1]].append(v[0])
        V[v[0]].append(v[1])
    st1 = set()
    st1.add(n-1)
    q = [n-1]
    while len(q) > 0:
        t = q.pop(-1)
        for v in U[t]:
            if not v in st1:
                q.append(v)
                st1.add(v)
    st2 = set()
    st2.add(0)
    q = [0]
    while len(q) > 0:
        t = q.pop(-1)
        for v in V[t]:
            if not v in st2:
                q.append(v)
                st2.add(v)
    st = st1 & st2
    eg = []
    for v in G:
        if v[0] in st and v[1] in st:
            eg.append(v)
    ans = bellman_ford(0, n, eg)
    if ans is None:
        print(-1)
    else:
        print(max(0, -ans[n-1]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    inf = 1 << 60

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

    to = tuple(set() for _ in range(N))
    ot = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        to[a].add((b, -(c - P)))  # to,coin(負辺)
        ot[b].add((a, -(c - P)))  # to,coin(負辺)

    def reach(s, g, result):
        dq = deque()
        dq.append(s)
        while dq:
            v = dq.popleft()
            for u, _ in g[v]:
                if result[u]: continue
                result[u] = 1
                dq.append(u)

    reachable_from_N = [0] * N
    reachable_from_N[N - 1] = 1
    reach(N - 1, ot, reachable_from_N)

    reachable_from_1 = [0] * N
    reachable_from_1[0] = 1
    reach(0, to, reachable_from_1)

    unreachable = tuple(1 ^ (rn & r1) for rn, r1 in zip(reachable_from_N, reachable_from_1))

    def bellman_ford(dist):
        for _ in range(N):
            not_updated = True
            for v in range(N):
                for u, c in to[v]:
                    if unreachable[u]: continue
                    if (dist[v] == inf) or (dist[v] + c >= dist[u]): continue
                    dist[u] = dist[v] + c
                    not_updated = False
            if not_updated: return False

        for v in range(N):  # 負閉路検知
            for u, c in to[v]:
                if unreachable[u]: continue
                if (dist[v] == inf) or (dist[v] + c >= dist[u]): continue
                return True
        return False

    dist = [inf] * N
    dist[0] = 0
    cond = bellman_ford(dist=dist)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def Bellman_Ford(s, g, inf=1 << 60):
    # https://tjkendev.github.io/procon-library/python/graph/bellman-ford.html
    N = len(g)
    dist = [inf] * N
    dist[s] = 0
    for _ in range(N):
        not_updated = True
        for v in range(N):
            for u, c in g[v]:
                if (dist[v] == inf) or (dist[v] + c >= dist[u]): continue
                dist[u] = dist[v] + c
                not_updated = False

        if not_updated:
            return max(0, -dist[N - 1])

    # 負閉路が存在する
    for _ in range(N):
        not_updated = True
        for v in range(N):
            for u, c in g[v]:
                if (dist[v] == inf) or (dist[v] + c >= dist[u]): continue
                dist[u] = -inf
                not_updated = False
        if not_updated: break

    if dist[N - 1] == -inf:
        return -1
    else:
        return max(0, -dist[N - 1])


def main():
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, -(c - P)))  # to,coin(負辺)

    ret = Bellman_Ford(0, g)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, P = map(int, input().split())
from collections import deque,defaultdict
edge1 = [[] for _ in range(N)]
edge2 = [[] for _ in range(N)]
for i in range(M):
    a,b,c= map(int, input().split())
    edge1[a-1].append([b-1,P-c])
    edge2[b-1].append([a-1,P-c])
edges1 = set()
d = deque([0])
visited1 = defaultdict(lambda: False)
while len(d):
    v = d.popleft()
    for u,w in edge1[v]:
        if visited1[w*10**8+v*10**4+u] == False:
            visited1[w*10**8+v*10**4+u] = True
            edges1.add(w*10**8+v*10**4+u)
            d.append(u)
edges2 = set()
d = deque([N-1])
visited2 = defaultdict(lambda: False)
while len(d):
    v = d.popleft()
    for u,w in edge2[v]:
        if visited2[w*10**8+u*10**4+v] == False:
            visited2[w*10**8+u*10**4+v] = True
            edges2.add(w*10**8+u*10**4+v)
            d.append(u)
new_edge = list(edges1&edges2)
d = [10**10]*N
d[0] = 0
n = 0
while True:
    n += 1
    update = False
    for e in new_edge:
        w = e//10**8
        v = e%10**8//10**4
        u = e%10**4
        if d[u]>d[v]+w:
            d[u] = d[v]+w
            update = True
    if update == False:
        break
    if n==N and update==True:
        print(-1)
        exit()
print(max(0,-d[-1]))

Submission status: Accepted

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

from collections import deque

def dfs(s, lis):
    checked = [0]*N
    stack = deque([(s, 0)])
    while stack:
        v, c = stack.pop()
        if checked[v]!=0:
            continue
        checked[v] = 1
        for i in lis[v]:
            if checked[i]==0:
                stack.append((i, c+1))
    return checked

posc = dfs(0, pos)
negc = dfs(N-1, neg)
used = [0]*N
for i, (p, n) in enumerate(zip(posc, negc)):
    if p and n:
        used[i] = 1

def BellmanFord(s):
    inf = 10**18
    dist=[inf for i in range(N)]
    dist[s]=0
    for i in range(N):
        for edge in Edges:
            if used[edge[0]]==0 or used[edge[1]]==0:
                continue
            if edge[0] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i>=N-1:
                    return []
    return dist

d = BellmanFord(0)
if len(d)==0:
    print(-1)
else:
    print(max(0, -d[-1]))

Submission status: Accepted

Solution code:
def shortest_path(s):
  dist[s]=0
  for _ in range(n):
    for fr,to,cost in edge:
      if dist[fr]!=inf and dist[to]>dist[fr]+cost:
        dist[to]=dist[fr]+cost

def find_negative_loops():
  for _ in range(n):
    for fr,to,cost in edge:
      if dist[fr]!=inf and dist[to]>dist[fr]+cost:
        dist[to]=dist[fr]+cost
        negative[to]=True
      if negative[fr]:negative[to]=True

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=float("inf")
dist=[inf]*n
negative=[False]*n
shortest_path(0)
find_negative_loops()
print(-1) if negative[-1] else print(max(-dist[-1],0))

Submission status: Accepted

Solution code:
n,m,p=map(int,input().split())
E=[list(map(int,input().split())) for i in range(m)]
INF=float("inf")
dist=[INF]*n
dist[0]=0
prev=0
# 閉路の長さの最大はnなので2*n回ループさせれば閉路検出ができる
for i in range(2*n):
  for fr,to,cost in E:
    fr,to=fr-1,to-1
    cost*=-1
    cost+=p
    if dist[fr]!=INF and dist[to]>dist[fr]+cost:
      dist[to]=dist[fr]+cost
      if i>=n:
        dist[to]=-float("inf")
    if i==n-1:
      prev=dist[n-1]
if prev==dist[n-1]:
  print(max(-dist[n-1],0))
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000) #これがないと再帰の回数オーバーでエラー出る。
N,M,P = map(int,input().split())
N-=1 #頂点番号を0スタートに。ただし頂点数はN+1となることに注意。
INF = float("inf")
edge = []
to = [[] for _ in range(N+1)] #普通に移動できる点
rto = [[] for _ in range(N+1)] #逆に戻れる点
reachablefrom = [False for _ in range(N+1)] #始点0から終点N-1へ行けるかチェック
reachableto = [False for _ in range(N+1)] #終点N-1から始点0へ戻れるかチェック
OK = [False for _ in range(N+1)] #どちらからもいける点を検出。ここ以外の点はどうでもよい。
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1 #頂点番号を0スタートに
  c-=P #ここで先に最後に払う分を引いておく。
  c = -c #最短経路にしたいのでコストを負にする。
  edge.append((a,b,c))
  to[a].append(b)
  rto[b].append(a)

def dfs(v):
  if reachablefrom[v]:
    return
  reachablefrom[v] = True
  for u in to[v]:
    dfs(u)

def rdfs(v):
  if reachableto[v]:
    return
  reachableto[v] = True
  for u in rto[v]:
    rdfs(u)
    
dfs(0)
rdfs(N)
for i in range(len(OK)): #len(OK)でもまあ良いか。
  OK[i] = reachablefrom[i]&reachableto[i]
#ここからベルマンフォード法
d = [INF for _ in range(N+1)]
d[0] = 0 #スタートのコストは0
upd = True #サイクルで更新の有無をチェック
step = 0
while upd:
  upd = False
  for i in range(M):
    a,b,c = edge[i]
    if not OK[a] or not OK[b]:
      continue
    new = d[a]+c
    if new < d[b]: #aから来たほうが最短
      upd = True
      d[b] = new
  step += 1
  if step > N+10: #最短経路が頂点の数よりも大きくなることない。
    print("-1")
    sys.exit()
ans = -d[N] #最後、コストをマイナスで戻す
ans = max(0,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000) #これがないと再帰の回数オーバーでエラー出る。
N,M,P = map(int,input().split())
N-=1 #頂点番号を0スタートに
INF = float("inf")
edge = []
to = [[] for _ in range(N+1)] #普通に移動できる点
rto = [[] for _ in range(N+1)] #逆に戻れる点
reachablefrom = [False for _ in range(N+1)] #始点0から終点N-1へ行けるかチェック
reachableto = [False for _ in range(N+1)] #終点N-1から始点0へ戻れるかチェック
OK = [False for _ in range(N+1)] #どちらからもいける点を検出。ここ以外の点はどうでもよい。
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1 #頂点番号を0スタートに
  c-=P #ここで先に最後に払う分を引いておく。
  c = -c #最短経路にしたいのでコストを負にする。
  edge.append((a,b,c))
  to[a].append(b)
  rto[b].append(a)

def dfs(v):
  if reachablefrom[v]:
    return
  reachablefrom[v] = True
  for u in to[v]:
    dfs(u)

def rdfs(v):
  if reachableto[v]:
    return
  reachableto[v] = True
  for u in rto[v]:
    rdfs(u)
    
dfs(0)
rdfs(N)
for i in range(len(OK)): #len(OK)でもまあ良いか。
  OK[i] = reachablefrom[i]&reachableto[i]
#ここからベルマンフォード法
d = [INF for _ in range(N+1)]
d[0] = 0 #スタートのコストは0
upd = True #サイクルで更新の有無をチェック
step = 0
while upd:
  upd = False
  for i in range(M):
    a,b,c = edge[i]
    if not OK[a] or not OK[b]:
      continue
    new = d[a]+c
    if new < d[b]: #aから来たほうが最短
      upd = True
      d[b] = new
  step += 1
  if step > N+1:
    print("-1")
    sys.exit()
ans = -d[N] #最後、コストをマイナスで戻す
ans = max(0,ans)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code

def resolve():
    N,M,P=pin()
    edge=[]#0-index
    for i in range(M):
        a,b,c=pin()
        edge.append((a-1,b-1,P-c))
    #print(edge)
    
    #Bellman–Ford algorithm?
    inf = float("inf")
    ans=[inf]*N#0-index
    ans[0]=0

    for i in range(N*2):
        for j in range(M):
            t,f,p=edge[j]
            ans[f]=min(ans[f],ans[t]+p)
            if  ans[f]>ans[t]+p:
                ans[f]=0-inf
    #    print(ans)
        if i==N:
            temp=ans[-1]
        if i==N*2-1:
            if ans[-1]<temp:
                ans[-1]=0-inf
    t=(0-ans[-1])
    



    if t==inf:s=-1
    elif t<0:s=0
    else:s=t
    print(s)
#%%submit!
resolve()

Submission status: Accepted

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

used1 = [0]*N
used1[0] = 1
from collections import deque
q = deque()
q.append(0)
while q:
    u = q.pop()
    for e in E[u]:
        if used1[e[0]] == 1:
            continue
        used1[e[0]] = 1
        q.append(e[0])

used2 = [0]*N
used2[N-1] = 1
q.append(N-1)
while q:
    u = q.pop()
    for e in E2[u]:
        if used2[e] == 1:
            continue
        used2[e] = 1
        q.append(e)

L = [0]*N
for i in range(N):
    L[i] = used1[i] & used2[i]
        
def BellmanFord(E, N, source):
    inf = 10**12
    d = [inf for _ in range(N)]
    d[source] = 0
    
    for i in range(N):
        for j in range(N):
            for edge in E[j]:
                if d[edge[0]] > d[j] + edge[1]:
                    d[edge[0]] = d[j] + edge[1]
                    if i == N-1 and L[edge[0]]== 1:
                        return -1
    
    return d

d = BellmanFord(E, N, 0)
if d == -1:
    print(-1)
else:
    print(max(0, -d[-1]))

Submission status: Accepted

Solution code:
from collections import deque

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

edges = [[] for _ in range(N)]
revEdges = [[] for _ in range(N)]
E = []
for _ in range(M):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    revEdges[to].append(fr)
    E.append((fr, to, -(cost - P)))

def canVisit(start, edges):
    st = deque([start])
    minDist = [10**18] * N
    minDist[start] = 0

    while st:
        now = st.popleft()
        d = minDist[now] + 1
        for to in edges[now]:
            if minDist[to] > d:
                minDist[to] = d
                st.append(to)

    return [True if minDist[to] < 10**18 else False for to in range(N)]

canForward = canVisit(0, edges)
canBack = canVisit(N - 1, revEdges)

minDist = [10**18] * N
minDist[0] = 0
for i in range(N + 1):
    for fr, to, cost in E:
        d = minDist[fr] + cost
        if minDist[to] > d:
            if i == N and canForward[fr] and canBack[to]:
                print(-1)
                exit()

            minDist[to] = d

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7
INF = 10 ** 18

N, M, P = map(int, input().split())
G = []
G_append = G.append

g = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    G_append((A, B, -C + P))
    g[A].append(B)

d = [INF] * (N + 1) #最短距離を記録しておくリスト
d[1] = 0
def find_negative_loop1(): #負の閉路が存在するかを確認
    for i in range(N):
        for j in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[j]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                #頂点の回数と同じだけループを回しても更新が起きる-->負の閉回路が存在
                if i == N-1:
                    return True #Trueの時, 負の閉路が存在
    return False #Falseの時, 負の閉路が存在しない

def find_negative_loop2(): #負の閉路が存在するかを確認
    check = [False] * (N + 1)
    for _ in range(N):
        for j in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[j]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                check[e[1]] = True
            if check[e[0]]:
                check[e[1]] = True
    return check[N]

#呼び出しスタート地点を入れる
if find_negative_loop1():
    if find_negative_loop2():
        print (-1)
    else:
        print (max(0, -d[N]))
else:
    print (max(0, -d[N]))

Submission status: Accepted

Solution code:
N,M,P = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
bs = [[] for _ in range(N)]
for a,b,c in ABC:
    a,b = a-1,b-1
    es[a].append((b,c-P))
    bs[b].append((a,c-P))

go_set = set([0])
stack = [0]
while stack:
    v = stack.pop()
    for to,_ in es[v]:
        if to in go_set: continue
        go_set.add(to)
        stack.append(to)

bk_set = set([N-1])
stack = [N-1]
while stack:
    v = stack.pop()
    for to,_ in bs[v]:
        if to in bk_set: continue
        bk_set.add(to)
        stack.append(to)

use = go_set & bk_set
K = len(use)
INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(K):
    for v in range(N):
        if v not in use: continue
        for to,c in es[v]:
            if to not in use: continue
            if d[to] > d[v] - c:
                d[to] = d[v] - c
                if i==K-1:
                    print(-1)
                    exit()
print(max(0, -d[-1]))