Problem:


Single Source Shortest Path (Negative Edges)

Input

An edge-weighted graph G (V, E) and the source r.

|V| |E| r
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1

|V| is the number of vertices and |E| is the number of edges in G. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the source of the graph.

si and ti  represent source and target vertices of i-th edge (directed) and di represents the cost of the i-th edge.

Output

If the graph contains a negative cycle (a cycle whose sum of edge costs is a negative value) which is reachable from the source r, print 

NEGATIVE CYCLE

in a line.

Otherwise, print

c0
c1
:
c|V|-1

The output consists of |V| lines. Print the cost of the shortest path from the source r to each vertex 0, 1, ... |V|-1 in order. If there is no path from the source to a vertex, print "INF". 

Constraints

 1 ≤ |V| ≤ 1000

 0 ≤ |E| ≤ 2000

 -10000 ≤ di ≤ 10000

 There are no parallel edges

 There are no self-loops

Sample Input 1

4 5 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

Sample Output 1

0
2
-3
-1

Sample Input 2

4 6 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
3 1 0

Sample Output 2

NEGATIVE CYCLE

Sample Input 3

4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

Sample Output 3

INF
0
-5
-3



Sample input:
4 5 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2


Sample output:
0
2
-3
-1

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class BellmanFord:
    INF = int(1e18)
    N = -1
    edge = []
    
    def __init__(self, N):
        self.N = N
        
    def add_edge(self, frm, to, cost):
        self.edge.append((frm, to, cost));
        
    def add_bi_edge(self, a, b, cost):
        self.add_edge(a, b, cost)
        self.add_edge(b, a, cost)
    
    def calcD(self, start):
        D = [self.INF] * self.N
        D[start] = 0
        update, cnt = True, 0
        while update:
            update = False
            cnt = cnt + 1
            if cnt > self.N:
                return None
            
            for frm, to, cost in self.edge:
                ncost = D[frm] + cost
                if D[frm] == self.INF or ncost >= D[to]:
                    continue
                D[to] = ncost
                update = True
                
        return D

# def SPFA(N, G, s):
#     dist = [INF] * N
#     cont = [0] * N
#     cnts = [0]* N

#     dist[s] = 0
#     cont[s] = 1
#     cnts[s] += 1
#     que = deque([s])
#     su = s; num = 1
#     while que:
#         v = que.popleft()
#         cont[v] = 0
#         d = dist[v]
#         su -= d
#         num -= 1
#         for w, c in G[v]:
#             r = d + c
#             if r < dist[w]:
#                 if not cont[w]:
#                     cnts[w] += 1
#                     if N <= cnts[w]:
#                         return None
#                     if que and r < que[0]:
#                         que.appendleft(w)
#                     else:
#                         que.append(w)
#                     cont[w] = 1
#                     su += r
#                     num += 1
#                     dist[w] = r
#                     while su < dist[que[0]]*num:
#                         que.append(que.popleft())
#                 else:
#                     su += r - dist[w]
#                     dist[w] = r
#     return dist

V, E, r = MAP()

std = [LIST() for _ in range(E)]
# edges = [[] for _ in range(V)]

# for s, t, d in std:
#     edges[s].append((t, d))

# dist = SPFA(V, edges, r)

# if not dist:
#     print("NEGATIVE CYCLE")
# else:
#     for i in range(V):
#         print(dist[i] if dist[i] < INF else "INF")

bf = BellmanFord(V)
for s, t, d in std:
    bf.add_edge(s, t, d)

ans = bf.calcD(r)

if not ans:
    print("NEGATIVE CYCLE")
else:
    for i in range(V):
        print ('INF' if ans[i] == bf.INF else ans[i])

Submission status: Accepted

Solution code:
def shortest_path_faster_algorithm(E, start):
    # ベルマンフォードの更新があるところだけ更新する感じのやつ
    # O(VE) だが実用上高速
    # E は隣接リスト
    # 検証: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4005805#1
    from collections import deque
    inf = float("inf")  # 10**18 は良くない
    N = len(E)
    q = deque([start])  # スタックにするとコーナーケースがあるっぽい
    distance = [inf] * N;  distance[start] = 0
    in_q = [0] * N;        in_q[start] = True
    times = [0] * N;       times[start] = 1
    while q:
        v = q.popleft()
        in_q[v] = False
        dist_v = distance[v]
        for u, cost in E[v]:
            new_dist_u = dist_v + cost
            if distance[u] > new_dist_u:
                times[u] += 1
                if times[u] >= N:  # 負閉路検出
                    print("NEGATIVE CYCLE"); exit()
                    distance[u] = -inf
                else:
                    distance[u] = new_dist_u
                if not in_q[u]:
                    in_q[u] = True
                    q.append(u)
    return distance

import sys
def main():
    N, M, r = map(int, sys.stdin.readline().split())
    E = [[] for _ in range(N)]
    for s, t, d in zip(*[iter(map(int, sys.stdin.read().split()))]*3):
        E[s].append((t, d))
    distance = shortest_path_faster_algorithm(E, r)
    for d in distance:
        if d == float("inf"):
            print("INF")
        else:
            print(d)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def make_adj_list(n, E):
    l = [[] for _ in range(n)] # 隣接リスト. 各要素は(コスト、to_node)
    for i in range(E):
        s, t, d = map(int, input().strip().split())
        l[s].append([d, t])
    return l

def bellman_ford(n, s, l):
    # s: start node, n: num of node
    # return True: negative cycle
    dist = [INF] * n
    dist[s] = 0
    for i in range(n):
        for v in range(n):
            for k in range(len(l[v])):
                cost, to = l[v][k]
                if dist[v] != INF and dist[to] > dist[v] + cost:
                    dist[to] = dist[v] + cost
                    if i == n-1:
                        return (True, dist)
    return (False, dist)

def main():
    v, e, r = map(int, input().strip().split())
    l = make_adj_list(v, e)
    is_negative_cycle, dist = bellman_ford(v, r, l)
    if is_negative_cycle:
        print("NEGATIVE CYCLE")
        return
    for d in dist:
        if d == INF:
            print('INF')
        else:
            print(d)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#A
#Bellman-Ford法(最短距離)
def BellmanFord(edges,num_v,source):#（辺と重みのリスト、頂点の数、始点(1-index)）
    #グラフの初期化
    inf=float("inf")
    dist=[inf for i in range(num_v)]
    dist[source]=0
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i==num_v-1: 
                  return -1 #負経路を検出
    return dist

V,E,r = map(int,input().split())
STD = [list(map(int,input().split())) for i in range(E)]

inf = float("inf")
dist = BellmanFord(STD,V,r)
if dist == -1:
    print("NEGATIVE CYCLE")
else:
    for d in dist:
        if d == inf:
          print("INF")
        else:
          print(d)

Submission status: Accepted

Solution code:
V,E,Start = map(int,input().split())
INF = 10**20
Edge = []
D = [INF]*V
for _ in range(E):
    Edge.append(list(map(int,input().split())))

D[Start] = 0
loop = 0
while True:
    update = False
    for i in range(E):
        fr   = Edge[i][0]
        to   = Edge[i][1]
        cost = Edge[i][2]

        if D[fr] != INF and D[to] > D[fr] + cost:
            D[to] = D[fr] + cost
            update = True
    if update == False:
        break

    loop += 1
    if loop > V:
        break

if loop > V:
    print('NEGATIVE CYCLE')
else:
    for d in D:
        if d == INF:
            print('INF')
        else:
            print(d)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import os
import sys


def main():
    V, E, R = read_ints()
    D = [tuple(read_ints()) for _ in range(E)]
    print(*solve(V, E, R, D), sep='\n')


def solve(V, E, R, D):
    INF = 10001 * 1000
    dists = [INF] * V
    dists[R] = 0
    for _ in range(V - 1):
        for s, t, d in D:
            if dists[s] != INF and dists[t] > dists[s] + d:
                dists[t] = dists[s] + d

    for s, t, d in D:
        if dists[s] != INF and dists[s] + d < dists[t]:
            return ['NEGATIVE CYCLE']

    return ['INF' if d == INF else d for d in dists]


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
v, e, r = map(int, input().split( ))
E = [[] for _ in range(v)]
inf = 10**12
for _ in range(e):
    s,t,d = map(int, input().split( ))
    E[s].append([t,d])


D = [inf for _ in range(v)]
D[r] = 0
"""
間違い
for ve in range(v):
    for ed in E[ve]:
        D[ed[0]] = min(D[ed[0]], D[ve] + ed[1])
    print(*D)
"""
for _ in range(v):
    for ve in range(v):
        for ed in E[ve]:
            D[ed[0]] = min(D[ed[0]], D[ve] + ed[1])

for i in range(v):
    if E[i]:
        for ed in E[i]:
            if D[i] + ed[1] < D[ed[0]] and D[ed[0]]<inf//10:
                print("NEGATIVE CYCLE")
                sys.exit()

for i in range(v):
    if D[i]<inf//100:
        print(D[i])
    else:
        print("INF")

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))

INF = int(1e18)

class BellmanFord:
  N = -1
  edge = []
  
  def __init__(self, N):
    self.N = N
  
  def addEdge(self, a, b, cost):
    self.edge.append((a, b, cost))
  
  def addBiEdge(self, a, b, cost):
    self.addEdge(a, b, cost)
    self.addEdge(b, a, cost)

  def calc(self, start):
    dist = [INF] * self.N
    dist[start] = 0
    update = True
    cnt = 0
    while update:
      update = False
      cnt += 1
      if cnt > self.N:
        return -INF
      for a, b, cost in self.edge:
        ncost = dist[a] + cost
        if dist[a] == INF or ncost >= dist[b]:
          continue
        dist[b] = ncost
        update = True
    return dist

def main():
  v, e, r = na()
  BF = BellmanFord(v)
  for _ in range(e):
    BF.addEdge(*na())

  ans = BF.calc(r)
  if ans == -INF:
    print("NEGATIVE CYCLE")
  else:
    for i in range(v):
      print('INF' if ans[i] == INF else ans[i])

main()

Submission status: Accepted

Solution code:
def SPFA(G:list, source=0):
	from collections import deque
	V = len(G)
	d = [float("inf")]*V
	inQ = [False]*V
	cnt = [0]*V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	_sum = 0
	_len = 1
	while Q:
		f = Q.popleft()
		inQ[f] = False
		_sum -= d[f]
		_len -= 1
		for t,c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					inQ[t] = True
					cnt[t] += 1
					if dist*_len < _sum:
						Q.appendleft(t)
					else:
						Q.append(t)
					_sum += dist
					_len += 1
				if cnt[t] > V:
					#negative cycle
					return None
	return d
	
def main():
	V,E,r,*L=map(int,open(0).read().split())
	G=[[]for _ in range(V)]
	for s,t,d in zip(*[iter(L)]*3):
		G[s].append((t,d))
	ret = SPFA(G,r)
	if ret==None:
		print("NEGATIVE CYCLE")
	else:
		for x in ret:
			print("INF" if x==float("inf") else x)
			
if __name__=="__main__":main()

Submission status: Accepted

Solution code:
from collections import deque

def find_negative_loop():
    INF = float('inf')
    V, E, r = map(int ,input().split())

    dist = [INF] * V
    dist[r] = 0    
    es = deque()
    
    for i in range(E):
        s, t, d = map(int, input().split())        
        es.append((s, t, d))
    
    for i in range(V):
        for e in es:
            f, t, c = e
            if dist[f] != INF and dist[t] > dist[f] + c:
                dist[t] = dist[f] + c
                if i == V - 1: return True, dist
    return False, dist

def main():
    INF = float('inf')
    is_negative, dist = find_negative_loop()
    
    if is_negative: print('NEGATIVE CYCLE')
    else:
        for d in dist:
            if d == INF: print('INF')
            else: print(d)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from typing import List, Tuple


if __name__ == "__main__":
    V, E, r = map(lambda x: int(x), input().split())

    edges: List[List[Tuple[int, int]]] = [[] for _ in range(V)]
    dists = [sys.maxsize for _ in range(V)]
    dists[r] = 0

    for _ in range(E):
        s, t, dist = map(lambda x: int(x), input().split())
        edges[s].append((t, dist))

    for _ in range(V):
        for vertex in range(V):
            if sys.maxsize != dists[vertex]:
                for to, cost in edges[vertex]:
                    if cost + dists[vertex] < dists[to]:
                        dists[to] = cost + dists[vertex]

    for vertex in range(V):
        if sys.maxsize != dists[vertex]:
            for to, cost in edges[vertex]:
                if cost + dists[vertex] < dists[to]:
                    # If dist can be smaller than previous one, there is negative cycle.
                    print("NEGATIVE CYCLE")
                    exit(0)

    for dist in dists:
        if sys.maxsize == dist:
            print("INF")
        else:
            print(dist)

Submission status: Accepted

Solution code:
from collections import deque
N, M, r = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    s, t, d = map(int, input().split())
    G[s].append((t, d))

INF = 10**18
def SPFA(N, G, s):
    dist = [INF] * N
    cont = [0] * N
    cnts = [0]* N

    dist[s] = 0
    cont[s] = 1
    cnts[s] += 1
    que = deque([s])
    su = s; num = 1
    while que:
        v = que.popleft()
        cont[v] = 0
        d = dist[v]
        su -= d
        num -= 1
        for w, c in G[v]:
            r = d + c
            if r < dist[w]:
                if not cont[w]:
                    cnts[w] += 1
                    if N <= cnts[w]:
                        return None
                    if que and r < que[0]:
                        que.appendleft(w)
                    else:
                        que.append(w)
                    cont[w] = 1
                    su += r
                    num += 1
                    dist[w] = r
                    while su < dist[que[0]]*num:
                        que.append(que.popleft())
                else:
                    su += r - dist[w]
                    dist[w] = r
    return dist
dist = SPFA(N, G, r)
if dist is None:
    print("NEGATIVE CYCLE")
else:
    for i in range(N):
        print(dist[i] if dist[i] < INF else "INF")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M, r = map( int, input().split())
    d = dict()
    E = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map( int, input().split())
        d[(a,b)] = c
        E[a].append(b)
    INF = 10**14*2
    V = [INF]*N
    V[r] = 0
    for _ in range(N-1):
        for e in d:
            s, t = e
            if V[s] + d[e] < V[t]:
                V[t] = V[s] + d[e]
    q = deque([r])
    W = [False]*N
    while q:
        v = q.pop()
        for w in E[v]:
            if W[w] == False:
                W[w] = True
                q.append(w)
    for e in d:
        s, t = e
        if V[s] + d[e] < V[t] and (W[s] == True or W[t] == True):
            print("NEGATIVE CYCLE")
            return
    for i in range(N):
        if V[i] >= 10**14:
            print("INF")
            continue
        print(V[i])
    # #if you want to know whether its path has negative cycle, we need followings.
    # E = [ V[i] for i in range(N)]
    # for _ in range(N-1):#probably OK, maybe N
    #     for e in d:
    #         s, t = e
    #         if E[s] + d[e] < E[t]:
    #             E[t] = E[s] + d[e]
    # #if you want to know whether its path has negative cycle, we need followings.
    # for i in range(N):
    #     if V[i] == E[i]:
    #         print(V[i])
    #     else:
    #         print("NEGATIVE CYCLE")
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    V, E, r = readi(3)
    edges = readi(E, 3)
    dist = arr(V, fill_value=INF)
    dist[r] = 0
    for i in range(V):
        for a, b, c in edges:
            new_d = dist[a] + c
            if new_d < dist[b]:
                dist[b] = new_d
                if i == V - 1:
                    print("NEGATIVE CYCLE")
                    return
    for i in range(V):
        print("INF" if dist[i] == INF else dist[i])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
"""
Bellman_Ford
単一始点最短経路を求める
g: グラフの隣接リスト
start: 始点
返り値: dist, is_OK (負回路なしならTrue)
"""
def Bellman_Ford(g,start):
    n = len(g)    
    dist = [float("inf")]*n
    dist[start] = 0
    
    for i in [0]*(n):
        updated = False
        for v in range(n):
            for to, cost in g[v]:
                if dist[to] <= dist[v] + cost: continue
                dist[to] = dist[v] + cost
                updated = True
        if not updated: break
    else: return None, False #n周更新された場合
    return dist, True        
    

"""
###############################################################
AOJ: GRL_1_B http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B

##############################################################
"""

v,e,r = [int(i) for i in input().split()]
std = [[int(i) for i in input().split()] for _ in range(e)]

g = [[] for _ in range(v)]
for s,t,d in std:
    g[s].append((t,d))


dist, tf = Bellman_Ford(g,r)
if tf:
    for i in dist:
        print(i if i != float("inf") else "INF")
else: print("NEGATIVE CYCLE")

Submission status: Accepted

Solution code:
v,e,r = map(int,input().split())
D = [float('inf')]*v
L = []
find_negative = False
for i in range(e):
    s,t,d = map(int,input().split())
    L.append([s,t,d])
D[r] = 0
for i in range(v):
    update = False
    for j in range(e):
        a,b,c = L[j][0],L[j][1],L[j][2]
        if D[b] > D[a]+c:
            D[b] = D[a]+c
            update = True
            if i == v-1:
                find_negative = True
                break
    if not update:
        break
if find_negative:
    print('NEGATIVE CYCLE')
else:
    for i in range(v):
        if D[i] == float('inf'):
            print('INF')
        else:
            print(D[i])

Submission status: Accepted

Solution code:
import math
inf = math.inf
negative_cycle_flag = False

def INITSS (G, s): # s means start
    # for u in G.V:
    #      u.d = inf
    #      u.pi = None
    G.V_d[s] = 0


def RELAX(u, v, w, V_d, V_pi):
    if V_d[v] > V_d[u] + w[u][v]:
        V_d[v] = V_d[u] + w[u][v]
        V_pi[v] = u


def BELLMANFORD (G, s, w):# w is weight matrix
    global negative_cycle_flag
    INITSS(G, s)
    for i in range(1,len(G.V_d)):
        for u, v in G.E:
            RELAX(u, v, w, G.V_d, G.V_pi)

    for u, v in G.E:
        if G.V_d[u] + w[u][v] < G.V_d[v]:
            negative_cycle_flag = True
            break

class Graph:
    def __init__(self, v_num, e_num, E):
        self.V_d = [inf for _ in range(v_num)]
        self.V_pi = [None for _ in range(v_num)]
        self.E = E

v_num, e_num, s = map(int, input().split())
E =[]
w = [[inf for _ in range(v_num)] for _ in range(v_num)]
for _ in range(e_num):
    u, v, weight = map(int, input().split())
    w[u][v] = weight
    E.append((u, v))

G = Graph(v_num, e_num, E)

BELLMANFORD(G, s, w)
if negative_cycle_flag == True:
    print("NEGATIVE CYCLE")
else:
    for k in range(v_num):
        if(G.V_d[k]==inf):
            print("INF")
        else:
            print(G.V_d[k])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 30 11:59:44 2019
Bellman Ford Method
@author: maezawa
"""

import collections


class BellmanFord():
    def __init__(self):
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed:
            self.edges.append([u, v, d])
        else:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])

    def BellmanFord_search(self, s):
        """
        次のBellmanFord_negative_boolまで考慮した時には、0-indexedであることに注意
        s =  始点
        return: d[i] 始点sから各点iまでの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                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:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes, start, zero_indexed=False):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = collections.defaultdict(lambda: float('inf'))
        d[start] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    #print(i, j, e)
                    if i == numNodes-1:
                        return True
        #print(d)
        return False
    

graph = BellmanFord()
num_v, num_edges, start = list(map(int, input().split()))

for i in range(num_edges):
    u, v, w = list(map(int, input().split()))
    graph.add(u, v, w, directed=True)

if graph.BellmanFord_negative_bool(num_v, start, zero_indexed=True):
    print('NEGATIVE CYCLE')
else:
    distances = graph.BellmanFord_search(start)
    for i in range(num_v):
        if distances[i] == float('inf'):
            print('INF')
        else:
            print(distances[i])

Submission status: Accepted

Solution code:
N,E,r=map(int,input().split())
G=[]
for i in range(E):
    s,t,d=map(int,input().split())
    G.append([d,s,t])
def bellman_ford(G,s):
    INF=10**9
    d=[INF]*N
    d[s]=0
    j=0
    while(True):
        update=False
        for i in range(E):
            cost,fro,to=G[i]
            if d[fro]!=INF and d[to]>d[fro]+cost:
                d[to]=d[fro]+cost
                update=True
                if j==N-1:
                    return True,0#負の閉路あり
        j+=1
        if not(update):
            break
    return False,d#負の閉路なし、ｓからの最短距離ｄ
bool,d=bellman_ford(G,r)
if bool:
    print("NEGATIVE CYCLE")
else:
    for i in range(N):
        if d[i]==10**9:
            print("INF")
        else:
            print(d[i])

Submission status: Accepted

Solution code:
from collections import defaultdict

def bellman_ford(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = {i: defaultdict(int) for i in range(N)}
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = [INF]*N
    prev = [-1]*N
    dist[s] = 0
    for n_iterations in range(N):
        updated = False
        for v in V:
            d = dist[v]
            if d != INF:
                for u, c in E[v].items():
                    temp = d + c
                    if dist[u] > temp:
                        updated = True
                        dist[u] = temp
                        prev[u] = v
        if not updated: # the minimum costs are already stored in dist
            break
    else: # the above loop is not broken if and only if there exists a negative cycle
        return None
    return dist

INF = float('inf')
N, M, r = map(int, input().split())
E = {i: defaultdict(int) for i in range(N)}
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a][b] = c
V = list(range(N))
dist = bellman_ford(V, E, r)
if dist is None:
    print('NEGATIVE CYCLE')
else:
    for d in dist:
        if d == INF: print('INF')
        else: print(d)

Submission status: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(100000)

# ---- belmann-ford -----
V_num, E_num, r = [int(ele) for ele in input().split()]
adjc_list = []
edges = []
for _ in range(V_num):
    adjc_list.append([])

for _ in range(E_num):
    src, dst, w = [int(ele) for ele in input().split()]
    adjc_list[src].append([w, dst])
    edges.append([src, dst, w])

INF = 99999999999999
d = [INF for _ in range(V_num)]
d[r] = 0

# ---- dfs ----
stack = collections.deque()
yet = [ele for ele in range(V_num)]


def main():
    global edges
    # 連結成分の調査
    stack.clear()
    stack.appendleft(r)
    dfs(stack)
    # yet に残っているやつは非連結成分なので、bellman_fordの探索する辺リストから除外する
    edges = list(filter(lambda e: e[0] not in yet and e[1] not in yet, edges))
    output_ans() if bellman_ford() != -1 else print("NEGATIVE CYCLE")


def dfs(stack):
    if not stack:
        return

    n = stack[0]
    yet.remove(n)

    for _, dst in adjc_list[n]:  # stackの表面
        if dst in yet:  # 未訪問なら
            stack.appendleft(dst)
            dfs(stack)
    else:
        stack.popleft()


def bellman_ford():
    for _ in range(V_num - 1):
        for src, dst, w in edges:
            if d[dst] > w + d[src]:
                d[dst] = w + d[src]

    for src, dst, w in edges:
        if d[dst] > w + d[src]:
            return -1

    return


def output_ans():
    for d_i in d:
        if d_i == INF:
            print("INF")
        else:
            print(d_i)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
V, E, r = map(int, input().split())
inf = 2**32
e = []
for i in range(E):
    s, t, d = map(int, input().split())
    e.append([s, t, d])

# 始点からの距離初期化
distance = [inf]*V
distance[r] = 0

'''
ベルマンフォード法による単一最短経路
負の重みがある場合でも大丈夫だが、負の重みがない場合はダイクストラのほうがよい
O(V*E)
'''


def bellmanFord():
    for v in range(V):
        updated = False
        for s, t, d in e:
            if distance[s] != inf and (distance[s]+d) < distance[t]:
                distance[t] = distance[s]+d
                updated = True
        if v == (V-1) and updated:
            return False
    return True


b = bellmanFord()
if b:
    for v in range(V):
        print(distance[v] if distance[v] != inf else "INF")
else:
    print("NEGATIVE CYCLE")

Submission status: Accepted

Solution code:
import sys
from math import isinf
# どれが終点の時に負の閉路があるかをnegative[v]にいれる
# dists = [float('inf')] * V # 到達不能はinf
# negatives = [False] * V

def bellman_ford(start:int)->bool:
    """ ベルマンフォード O(|V|*|E|)
    :param V:      頂点数
    :param edges:  辺 [(始点，終点，重み)]
    :param start:  始点
    """
    global dists, negatives
    global edges
    dists[start] = 0
    V = len(dists)
    for i in range(V):
        for (s, t, w) in edges:
            if isinf(dists[s]): continue
            if dists[t] > dists[s] + w:
                dists[t] = dists[s] + w
                if i==V-1:
                    negatives[t] = True


if __name__ == "__main__":
    V,E,start = map(int, input().split())
    edges = []
    for _ in range(E):
        s,t,d = map(int, input().split())
        edges.append((s,t,d))

    dists = [float('inf')] * V # 到達不能はinf
    negatives = [False] * V
    bellman_ford(start)
    if any(neg for neg in negatives)==True:
        print("NEGATIVE CYCLE")
        exit()
    for di in dists:
        if di==float('inf'):
            print("INF")
        else:
            print(di)

Submission status: Accepted

Solution code:
INF = float('inf')

def bellman_ford(graph, weights, s):
  d = {v: INF for v in graph}
  d[s] = 0
  edges = [(u, v) for u, vs in graph.items() for v in vs]
  for _ in range(len(graph) - 1):
    for (u, v) in edges:
      d_temp = d[u] + weights[u, v]
      if d_temp < d[v]:
        d[v] = d_temp

  for (u, v) in edges:
    if d[u] + weights[u, v] < d[v]:
      print('NEGATIVE CYCLE')
      return None
  return d


n_vertex, n_edge, s = [int(x) for x in input().split()]
graph = {i: [] for i in range(n_vertex)}
weights = {}
for i in range(n_edge):
    u, v, w = [int(x) for x in input().split()]
    graph[u].append(v)
    weights[u, v] = w

d = bellman_ford(graph, weights, s)

if d is not None:
    for i in range(n_vertex):
        print(d[i] if d[i] is not INF else 'INF')

Submission status: Accepted

Solution code:
def bellman_ford():
    edges = []
    inf = 1

    n, m, s = map(int, input().split())

    for i in range(m):
        src, tgt, cost = map(int, input().split())
        edges.append({'source': src, 'target': tgt, 'cost': cost})
        if cost > 0:
            inf += cost

    graph = [{'cost': inf, 'source': -1} for i in range(n)]
    graph[s]['cost'] = 0

    for i in range(n - 1):
        for edge in edges:
            src = edge['source']
            tgt = edge['target']
            if graph[src]['cost'] == inf:
                continue
            if graph[tgt]['cost'] > graph[src]['cost'] + edge['cost']:
                graph[tgt]['cost'] = graph[src]['cost'] + edge['cost']
                graph[tgt]['source'] = src

    for edge in edges:
        src = edge['source']
        tgt = edge['target']
        if graph[src]['cost'] == inf:
            continue
        if graph[tgt]['cost'] > graph[src]['cost'] + edge['cost']:
            print('NEGATIVE CYCLE')
            return

    for vertex in graph:
        print(vertex['cost']) if vertex['cost'] < inf else print('INF')


bellman_ford()