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:
from collections import deque
import sys
input = sys.stdin.readline


def main():
    N, M, P = map(int, input().split())
    edge = [[] for _ in range(N)]
    redge = [[] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        C -= P
        C = -C
        edge[A].append((B,C))
        redge[B].append(A)

    # 0 => N-1の間にある閉路を検出したいので
    # 0とN-1からたどりつけない場所は前処理で取り除く
    
    visited1, visited2 = {0}, {N-1}
    
    stack = [0]
    while stack:
        v = stack.pop()
        for dest, _ in edge[v]:
            if dest in visited1:
                continue
            visited1.add(dest)
            stack.append(dest)
    
    stack = [N-1]
    while stack:
        v = stack.pop()
        for dest in redge[v]:
            if dest in visited2:
                continue
            visited2.add(dest)
            stack.append(dest)
    
    OK = visited1 & visited2
    
    new_edge = [[] for _ in range(N)]
    for s in range(N):
        for t, c in edge[s]:
            if t in OK:
                new_edge[s].append((t,c))

    flag = True
    d = [float('inf')] * N
    d[0] = 0
    #ベルマンフォード法、N回実行してまだ更新されている場合は負の閉路が存在する
    for _ in range(N):
        flag = False
        for v, e in enumerate(new_edge):
            for t, c in e:
                if d[v] != float('inf') and d[v] + c < d[t]:
                    d[t] = d[v] + c
                    flag = True
        if not flag:
            print(max(0,-d[N-1]))
            exit()
    else:
        print(-1)
        exit()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix, lil_matrix
from scipy.sparse.csgraph import bellman_ford, NegativeCycleError


def main():
    N, M, P = map(int, input().split())
    A, B, C = [0] * M, [0] * M, [0] * M
    v = [set() for _ in range(N)]
    u = [set() for _ in range(N)]
    for i in range(M):
        a, b, c = map(int, input().split())
        A[i], B[i], C[i] = a - 1, b - 1, P - c
        u[a - 1].add(b - 1)
        v[b - 1].add(a - 1)
    vv = set()
    cur = set([N - 1])
    while cur:
        vv |= cur
        cur = set().union(*(v[c] for c in cur)) - vv
    uu = set()
    cur = set([0])
    while cur:
        uu |= cur
        cur = set().union(*(u[c] for c in cur)) - uu
    reachable = vv & uu
    l = {}
    for a, b, c in zip(A, B, C):
        if a in reachable and b in reachable:
            l[(a, b)] = min(c, l.get((a, b), 10 **9))
    AA, BB, CC = [], [], []
    for (a, b), c in l.items():
        AA.append(a)
        BB.append(b)
        CC.append(c)
    mx = csr_matrix((CC, (AA, BB)), shape=(N, N))
    try:
        dm = bellman_ford(mx, indices=[0])
    except NegativeCycleError:
        return -1
    return max(0, -int(dm[0][N - 1]))


print(main())

Submission status: Accepted

Solution code:
import sys
import math
import heapq
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) 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 II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M,P=LI()
EDGES = []
E1 = [[] for i in range(N+1)]
E2 = [[] for i in range(N+1)]

for i in range(M):
    F,T,C=LI()
    EDGES.append((F,T,P-C))
    E1[F].append(T)
    E2[T].append(F)

def bellman_ford(edges):
    # print(edges)
    DIST=[10**18]*(N+1)
    DIST[1] = 0
    for i in range(N):
        for j in range(len(edges)):
            fr, to, cost = edges[j]
            if (DIST[to] > DIST[fr] + cost):
                if (i == N-1):
                    print(-1)
                    exit()
                else:
                    DIST[to] = DIST[fr] + cost
    # print(DIST)
    print(max(-DIST[-1], 0))

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

use = dfs(E1,1) & dfs(E2, N)
# print(use)
bellman_ford([(a,b,c) for a,b,c in EDGES if (a in use and b in use)])

Submission status: Accepted

Solution code:
N,M,P = map(int,input().split())
E = []
for i in range(M):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  c=-c+P
  E.append([a,b,c])
  
def BellmanFord(s,g):
  #グラフの初期化
  inf=float("inf")
  dist=[inf for i in range(N)]
  dist[s]=0
  rout=[]
  
  #辺の緩和
  for i in range(N):
    for edge in E:
      if dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
        if i==N-1: dist[edge[1]]=-inf
  for i in range(N):
    for edge in E:
      if dist[edge[1]] > dist[edge[0]] + edge[2]:
        dist[edge[1]] = dist[edge[0]] + edge[2]
  if dist[g] == -inf:return -1
  return max(0,-dist[g])
print(BellmanFord(0,N-1))

Submission status: Accepted

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


def main():
    n, m, p = map(int, input().split())

    nodes = []
    for _ in range(m):
        a, b, c = map(int, input().split())
        nodes.append((a - 1, b - 1, -(c - p)))
    
    d = [float("inf") for _ in range(n)]
    pre = [-1 for _ in range(n)]
    d[0] = 0
    for _ in range(n):
        for nod in nodes:
            if d[nod[1]] > d[nod[0]] + nod[2]:
                d[nod[1]] = d[nod[0]] + nod[2]
                pre[nod[1]] = nod[0]

    for i, nod in enumerate(nodes):
        if d[nod[1]] > d[nod[0]] + nod[2]:
            nodes[i] = (nod[0], nod[1], -float('inf'))
    
    d = [float("inf") for _ in range(n)]
    pre = [-1 for _ in range(n)]
    d[0] = 0
    for _ in range(n):
        for nod in nodes:
            if d[nod[1]] > d[nod[0]] + nod[2]:
                d[nod[1]] = d[nod[0]] + nod[2]
                pre[nod[1]] = nod[0]

    path = set()
    fr = n - 1
    while pre[fr] != -1:
        if fr in path:
            break
        path.add(pre[fr])
        fr = pre[fr]

    for nod in nodes:
        if d[nod[1]] > d[nod[0]] + nod[2]:
            if nod[0] in path:
                print(-1)
                return

    if d[n - 1] == -float('inf'):
        print(-1)
        return 

    if d[n - 1] > 0:
        print(0)
    else:
        print(-d[n - 1])
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys

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

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

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

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

res = bellman_ford(N, edges, 0)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,m,p=map(int,input().split())
g=[[] for _ in range(n)]
g2=[[] for _ in range(n)]
g3=[[] for _ in range(n)]
for _ in range(m):
    a,b,l=map(int,input().split())
    g[a-1].append([b-1,p-l])
    g2[a-1].append(b-1)
    g3[b-1].append(a-1)

f1=[False for _ in range(n)]
def dfs1(s):
    global f1
    global g2
    f1[s] = True
    for sg in g2[s]:
        if not f1[sg]:
            dfs1(sg)
f2=[False for _ in range(n)]
def dfs2(s):
    global f2
    global g3
    f2[s] = True
    for sg in g3[s]:
        if not f2[sg]:
            dfs2(sg)

dfs1(0)
dfs2(n-1)
f3 = []
for i in range(n):
    f3.append(f1[i] and f2[i])

def bellman_ford(g,n):
    INF = 10**10
    res = [INF for _ in range(n)]
    res[0] = 0
    for _ in range(n-1):
        for i in range(n):
            if res[i] != INF:
                for sa,sb in g[i]:
                    res[sa] = min(res[sa],res[i]+sb)
    ret = res[-1]
    for i in range(n):
        if res[i] != INF:
            for sa,sb in g[i]:
                if res[sa]>res[i]+sb:
                    if f3[sa]:
                        return False
    return ret

res = bellman_ford(g,n)
if type(res) == bool:
    print(-1)
elif res > 0:
    print(0)
else:
    print(res * -1)

Submission status: Accepted

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

n,m,p=map(int,input().split())
g=[[] for _ in range(n)]
g2=[[] for _ in range(n)]
g3=[[] for _ in range(n)]
for _ in range(m):
    a,b,l=map(int,input().split())
    g[a-1].append([b-1,p-l])
    g2[a-1].append(b-1)
    g3[b-1].append(a-1)

f1=[False for _ in range(n)]
def dfs1(s):
    global f1
    global g2
    f1[s] = True
    for sg in g2[s]:
        if not f1[sg]:
            dfs1(sg)
f2=[False for _ in range(n)]
def dfs2(s):
    global f2
    global g3
    f2[s] = True
    for sg in g3[s]:
        if not f2[sg]:
            dfs2(sg)

dfs1(0)
dfs2(n-1)
f3 = []
for i in range(n):
    f3.append(f1[i] and f2[i])

def bellman_ford(g,n):
    INF = 10**10
    res = [INF for _ in range(n)]
    res[0] = 0
    for _ in range(n-1):
        for i in range(n):
            if res[i] != INF:
                for sa,sb in g[i]:
                    res[sa] = min(res[sa],res[i]+sb)
    ret = res[-1]
    for i in range(n):
        if res[i] != INF:
            for sa,sb in g[i]:
                if res[sa]>res[i]+sb:
                    if f3[sa]:
                        return False
    return ret

res = bellman_ford(g,n)
if type(res) == bool:
    print(-1)
elif res > 0:
    print(0)
else:
    print(res * -1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m,p=map(int,input().split())
    E=[[] for _ in range(n)]
    R=[[] for _ in range(n)]
    for _ in range(m):
        u,v,c=map(int,input().split())
        u-=1; v-=1
        E[u].append((v,p-c))
        R[v].append((u,p-c))

    # 0 から到達できる点、N-1 から逆辺で到達できる点を列挙
    state=[0]*n
    state[0]+=1
    state[-1]+=2

    Q=[0]
    while(Q):
        v=Q.pop()
        for nv,w in E[v]:
            if(state[nv]&1): continue
            state[nv]+=1
            Q.append(nv)

    Q=[n-1]
    while(Q):
        v=Q.pop()
        for nv,w in R[v]:
            if(state[nv]&2): continue
            state[nv]+=2
            Q.append(nv)

    # state が 3 の辺だけを用いて Bellman Ford
    dist=[INF]*n
    dist[0]=0
    for k in range(n):
        update=False
        for v in range(n):
            if(state[v]!=3): continue
            for nv,w in E[v]:
                if(state[nv]!=3): continue
                if(dist[nv]>dist[v]+w):
                    dist[nv]=dist[v]+w
                    update=True
        if(not update):
            break
        if(update and k==n-1):
            print(-1)
            return

    print(max(0,-dist[-1]) if(dist[-1]!=INF) else -1)
resolve()

Submission status: Accepted

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

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

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


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


bellman_ford(n, 0, e)

Submission status: Accepted

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

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

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


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


bellman_ford(n, 0, e)

Submission status: Accepted

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

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

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

show_flg=False
show_flg=True


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

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

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

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

Submission status: Accepted

Solution code:
def BellmanFord(edges,num_v,source):
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  for i in range(num_v):
    for edge in edges:
      if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
        if i==num_v-1: dist[edge[1]-1] = -inf
  for i in range(num_v):
    for edge in edges:
      if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
  r = dist[-1]
  if r > 0: r = 0
  if r < 0: r=-r
  if r == inf: r=-1
  return r

import sys
input = sys.stdin.readline
N, M, P = map(int, input().split())
edges = []
for i in range(M):
    A, B, C = map(int, input().split())
    edges.append([A, B, P-C])
print(BellmanFord(edges, N, 1))

Submission status: Accepted

Solution code:
from collections import deque

N,M,P = map(int, input().split())
E = [[] for _ in range(N)]
Ei = [[] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int, input().split())
    E[a-1].append((b-1, -c+P))
    Ei[b-1].append(a-1)
    
q = deque()
q.append(0)
used = [0]*N
used[0] = 1
while q:
    t = q.pop()
    for e in E[t]:
        if used[e[0]] == 1:
            continue
        used[e[0]] = 1
        q.append(e[0])
        
q.append(N-1)
used2 = [0]*N
used2[N-1] = 1
while q:
    t = q.pop()
    for e in Ei[t]:
        if used2[e] == 1:
            continue
        used2[e] = 1
        q.append(e)
        
L = [0]*N
for i in range(N):
    if used[i] == 1 and used2[i] == 1:
        L[i] = 1
    
def BellmanFord(E, N, source):
    inf = 10**10
    d = [inf for _ in range(N)]
    d[source] = 0
    for i in range(N):
        for j in range(N):
            e = E[j]
            if len(e) == 0:
                continue
            for edge in e:
                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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m,p=map(int,input().split())
    E=[[] for _ in range(n)]
    R=[[] for _ in range(n)]
    for _ in range(m):
        u,v,c=map(int,input().split())
        u-=1; v-=1
        E[u].append((v,p-c))
        R[v].append((u,p-c))

    # 0 から到達できる点、かつ n-1 から逆辺で到達できる点を計算
    state=[0]*n
    state[0]+=1
    state[n-1]+=2

    # from 0
    Q=[0]
    while(Q):
        v=Q.pop()
        for nv,w in E[v]:
            if(state[nv]&1): continue
            state[nv]+=1
            Q.append(nv)

    # to n-1
    Q=[n-1]
    while(Q):
        v=Q.pop()
        for nv,w in R[v]:
            if(state[nv]&2): continue
            state[nv]+=2
            Q.append(nv)

    # state[v]==3 を結ぶ頂点のみを用いてBellman-Ford
    dist=[INF]*n
    dist[0]=0
    for k in range(n):
        flag=0
        for v in range(n):
            for nv,w in E[v]:
                if(state[v]&state[nv]!=3): continue
                if(dist[nv]>dist[v]+w):
                    dist[nv]=dist[v]+w
                    flag=1
        if(flag and k==n-1):
            print(-1)
            return

    print(max(-dist[-1],0))
resolve()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))

def bellman_ford(start, goal, N, edges,
                 get_route=False,
                 negative_loop=None,
                 start_distance=0,
                 plus_func=lambda D,d: D+d):
    '''
    goal: int or list or set
    edges: list or dict
        edges[x] = {(y0, distance0), ...}
    '''
    distance = [None]*N
    predecessor = [None]*N
    if isinstance(goal, int):
        goal = [goal]
    elif isinstance(goal, set):
        goal = list(goal)
    M = len(goal)
    goalable = [[False]*N for _ in range(M)]
    for m in range(M):
        goalable[m][goal[m]] = True
    distance[start] = start_distance
    for _ in range(N-1):
        for i in range(N):
            if distance[i] is None:
                continue
            for j, d in edges[i]:
                for m in range(M):
                    if goalable[m][j]:
                        goalable[m][i] = True
                p = plus_func(distance[i], d)
                if distance[j] is None or distance[j] > p:
                    distance[j] = p
                    predecessor[j] = i

    goal_valid = [True]*M
    for i in range(N):
        if distance[i] is None:
            continue
        for j, d in edges[i]:
            if distance[j] is not None and plus_func(distance[i], d) < distance[j]:
                # Negative loop detected.
                for m in range(M):
                    if goal_valid[m] and goalable[m][i]:
                        distance[goal[m]] = negative_loop
                        goal_valid[m] = False
    if get_route:
        return distance, predecessor
    else:
        return distance

N, M, P = inpl()
uv = [ set() for _ in range(N) ]
for i in range(M):
    a, b, c = inpl()
    a -= 1
    b -= 1
    uv[a].add((b,-c+P))

distance = bellman_ford(0, N-1, N, uv)
minus_ans = distance[-1]
if minus_ans is None:
    print(-1)
elif minus_ans > 0:
    print(0)
else:
    print(-minus_ans)

Submission status: Accepted

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

es = []

for i in range(M):
    a,b,c = map(int, input().split())
    es.append((a-1, b-1, c))

INF = float("inf")

d = [INF for _ in range(N)] 
d[0] = 0
"""
頂点Nに向かうまでに関係ない閉路に注意する

無限にコインを拾える場合、
・ある閉路を一周したときの得点と支払いの収支がプラス
・その閉路からゴールまで行ける
である。これがない場合、全てのノードを経由してゴールまで行く（N-1回移動）までにコインの枚数が最大になる
なので、一回ベルマンフォード法をやった後もう一回行って一回目と２回目でゴールまでのコイン枚数に変化があればゴ、
ールに行くまでの道に無限にコインをとれる閉路があるといえる

"""

def solve(start, f):
    for i in range(N):
        for a,b,c, in es:
            if d[a] != INF and d[a] + (-c) + P < d[b]:
                # ２週目と区別する。２週目で更新される部分は-INFとか適当に置いておくと、ゴールまでの影響がわかる
                if f == 0:
                    d[b] = d[a] + (-c) + P
                else:
                    d[b] = -INF


    return d[-1]


first=solve(0,0)
second=solve(0, 1)
if first != second:
    print(-1)
else:
    print(max(-first, 0))

Submission status: Accepted

Solution code:
inf = float('inf')
# ベルマンフォード法
# 計算量O(VE) V:頂点数, E:辺の数
# [引数]   n:頂点数, edges:辺集合, start:始点, end:終点
# [返り値] dist:startからの最短距離, exists_negative_cycle: 負閉路が存在するかどうか
def bellmanford(n : int, edges : list, start : int, goal : int) -> (list, bool):
    dist = [inf] * n
    dist[start] = 0
    exist_negative_cycle = False

    # 負閉路を含まないとき、頂点数nなら更新は高々n-1回で済む
    for _ in range(n-1):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w


    # (1)グラフに負閉路が含まれるときの検出
    # N回目で更新があったとき、グラフは負閉路を含む
    # for v, nv, w in edges:
    #     if dist[nv] > dist[v] + w:
    #         exists_negative_cycle = True

    # (2)startとgoalのパスに負閉路が含まれるときの検出
    is_updated = [False] * n
    for _ in range(n):
        for v, nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                is_updated[nv] = True
            if is_updated[v] is True:
                is_updated[nv] = True

    exist_negative_cycle = is_updated[goal]

    return dist, exist_negative_cycle

N, M, P = map(int,input().split())
edges = []
for _ in range(M):
    A, B, C = map(int,input().split())
    A -= 1; B -= 1
    C = C - P
    edges.append((A, B, -C))
 
dist, exist_negative_cycle = bellmanford(N, edges, 0, N-1)
 
if exist_negative_cycle is True:
    ans = -1
else:
    ans = max(-dist[N-1], 0)
 
print(ans)

Submission status: Accepted

Solution code:
# 到達可能な頂点の集合
def reachable_nodeset(start, inc):
  reachable = set()
  reachable.add(start)
  nodes = [start]
  
  while nodes:
    n = nodes.pop()
    for i in inc[n]:
      if i not in reachable:
        nodes.append(i)
        reachable.add(i)
  return reachable

def bellmanford(num, start, goal, edges):
  cost = [float('inf')]*num
  cost[start] = 0
  # 負の閉路が無ければ更新はV-1回までで終わる
  for _ in range(num):
    updated = False
    for a, b, c in edges:
      # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
      if cost[b] > cost[a]+c:
        cost[b] = cost[a]+c
        updated = True
    if not updated: break
  else:
    # V回目まで更新があったら負の閉路がある
    return -1
  return max(0, -cost[goal])

N, M, P = map(int, input().split())
to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]
edges = []

for _ in range(M):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  c = -(c-P)
  
  to[a].append(b)
  ot[b].append(a)
  edges.append((a,b,c))
  
reachableFromZero = reachable_nodeset(0, to)  
reachableToN = reachable_nodeset(N-1, ot)  
ok = reachableFromZero.intersection(reachableToN)
edges = tuple((a,b,c) for a,b,c in edges if a in ok and b in ok)

print(bellmanford(N, 0, N-1, edges))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    n,m,p=map(int,input().split())
    E=[[] for _ in range(n)]
    R=[[] for _ in range(n)]
    edges=[]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        R[b].append(a)
        edges.append((a,b,p-c))

    state=[0]*n
    state[0]=1
    state[n-1]=2

    Q=deque([0])
    while(Q):
        v=Q.popleft()
        for nv in E[v]:
            if(state[nv]&1): continue
            state[nv]+=1
            Q.append(nv)

    Q=deque([n-1])
    while(Q):
        v=Q.popleft()
        for nv in R[v]:
            if(state[nv]&2): continue
            state[nv]+=2
            Q.append(nv)

    dist=[INF]*n
    dist[0]=0
    for k in range(n):
        for a,b,w in edges:
            if(state[a]!=3 or state[b]!=3): continue
            if(dist[b]>dist[a]+w):
                dist[b]=dist[a]+w
                if(k==n-1):
                    print(-1)
                    return
    print(max(-dist[-1],0))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m,p=map(int,input().split())
    E=[[] for _ in range(n)]
    R=[[] for _ in range(n)]
    edges=[]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        R[b].append(a)
        edges.append((a,b,p-c))

    state=[0]*n

    def dfs(v):
        if(state[v]&1): return
        state[v]+=1
        for nv in E[v]: dfs(nv)
    dfs(0)

    def rdfs(v):
        if(state[v]&2): return
        state[v]+=2
        for nv in R[v]: rdfs(nv)
    rdfs(n-1)

    dist=[INF]*n
    dist[0]=0
    for k in range(n):
        for a,b,w in edges:
            if(state[a]!=3 or state[b]!=3): continue
            if(dist[b]>dist[a]+w):
                dist[b]=dist[a]+w
                if(k==n-1):
                    print(-1)
                    return
    print(max(-dist[-1],0))
resolve()