Problem:
Single Source Shortest Path (Negative Edges) Input An edge-weighted graph G ( V , E ) and the source r . | V | | E | r  s 0  t 0  d 0  s 1  t 1  d 1 : 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.  s i and t i represent source and target vertices of i -th edge (directed) and d i 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   c 0  c 1 : 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 ≤ d i ≤ 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

Solution (Python):

"""
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]
                
                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):
        
        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]
                    
                    if i == numNodes-1:
                        return True
        
        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])

Solution (Python):
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])

Solution (Python):
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: 
            break
    else: 
        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)

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


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


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


def main():
    global edges
    
    stack.clear()
    stack.appendleft(r)
    dfs(stack)
    
    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]:  
        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()

Solution (Python):
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")

Solution (Python):
import sys
from math import isinf




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

Solution (Python):
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')

Solution (Python):
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()

Solution (Python):
num_v,num_e,source=input().split()

edges=[]
verticies=[]

for i in range(int(num_e)):
    v,u,w=input().split()
    e=(int(v),int(u),int(w))
    edges.append(e)


for v in range(int(num_v)):
    v=str(v)
    verticies.append(v)

itn=int(num_v)-1
g=edges

dist=[float('inf')]*(itn+1)
dist[int(source)]=0


def BF(g):
    for i in range(itn):
        for edge in edges:
            v,u,w =edge
            if dist[v]!=float('inf'):
                if dist[v] + w < dist[u]:
                    dist[u]=dist[v] + w
                    
    
    ngc=0
    for edge in edges:
        v,u,w=edge
        if dist[v]!=float('inf'):
            if dist[v] + w < dist[u]:
                ngc=1
                 
                
    if ngc==0:
        for i in range(itn+1):
            if dist[i]==float('inf'):
                print("INF")
            else: print(dist[i])
    else:
        print("NEGATIVE CYCLE")

BF(g)

Solution (Python):
d=[]
v,e,r=list(map(int,input().split()))
edges=[list(map(int,input().split())) for i in range(e)]

def bellman_ford(s):
  global d
  d=[float('inf') for i in range(v)]
  d[s]=0

  for i in range(v-1):
    for s,t,w in edges:
      if d[t] > d[s]+w:
        d[t] = d[s]+w

  for s,t,w in edges:
    if d[s]+ w<d[t]:
      return False
  return True

if bellman_ford(r):
  for w in d:
    if w== float('inf'):
      print('INF')
    else:
      print(w)
else:
  print('NEGATIVE CYCLE')

Solution (Python):
def func(r, V, edge):
    c = [float("inf")] * V
    update = True
    loop = 0
    c[r] = 0
    while update:
        update = False
        for s in range(V):
            for t, d in edge[s]:
                temp = c[s] + d
                if temp < c[t]:
                    c[t] = temp
                    update = True

        loop += 1
        if loop == V:
            break
        
    if loop == V and update:
        c[r] = float("inf")

    return c
            

V, E, r = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    s, t, d = map(int, input().split())
    edge[s].append([t, d])

c = func(r, V, edge)

if c[r] == float("inf"):
    print("NEGATIVE CYCLE")
else:
    for temp in c:
        if temp == float("inf"):
            print("INF")
        else:
            print(temp)

Solution (Python):
import sys
fin = sys.stdin.readline


MAX_NUM = float('inf')

def initialize_int(adj, s):
    """
    assume that all vertex in {0, 1, 2, ..., N - 1}
    """
    N = len(adj)
    d = [MAX_NUM] * N
    d[s] = 0
    parent = [None] * N
    return d, parent


def relax(d, w, source_v, target_v, parent):
    new_cost = d[source_v] + w[source_v][target_v]
    if new_cost < d[target_v]:
        d[target_v] = new_cost
        parent[target_v] = source_v






def bellman_ford(adj, w, s):
    d, parent = initialize_int(adj, s)

    
    for _ in range(len(adj)):
        for vertex in range(len(adj)):
            for neighbor in adj[vertex]:
                relax(d, w, vertex, neighbor, parent)

    
    negative_cycle_edges = set()
    for vertex in range(len(adj)):
        for neighbor in adj[vertex]:
            if d[neighbor] > d[vertex] + w[vertex][neighbor]:
                negative_cycle_edges.add((vertex, neighbor))
    return d, parent, negative_cycle_edges



V, E, r = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(V)]
w = [[None] * V for _ in range(V)]
for _ in range(E):
    s, t, d = [int(elem) for elem in fin().split()]
    adj[s].append(t)
    w[s][t] = d

d, parent, negative_cycle_edges = bellman_ford(adj, w, r)
if len(negative_cycle_edges) > 0:
    print("NEGATIVE CYCLE")
else:
    for i in range(V):
        print("INF") if d[i] == MAX_NUM else print(d[i])

Solution (Python):

def input(f):
    global v, e, r, s, t, d, g
    
    v, e, r = map(int, f.readline().split())
    s = []
    t = []
    d = []
    for _ in range(e):
        s_, t_, d_ = map(int, f.readline().split())
        s.append(s_)
        t.append(t_)
        d.append(d_)
        
    g = [list() for _ in range(v)]
    for i in range(e):
        g[s[i]].append(i)

import os

if os.environ.get('ZEPPELIN_HOME'):
    import networkx as nx
    import matplotlib.pyplot as plt
    
    def visualize():
        G = nx.DiGraph()
        for i in range(v):
            G.add_node(i)
        for i in range(e):
            G.add_edge(s[i], t[i], t=d[i])
        
        plt.figure()
        plt.style.use('seaborn')
        plt.axis("off")
        pos = nx.spring_layout(G)
        nodes = nx.draw_networkx_nodes(G, pos, node_color='w', linewidths=2)
        nx.draw_networkx_labels(G, pos)
        nodes.set_edgecolor('black')
        nx.draw_networkx_edges(G, pos)
        nx.draw_networkx_edge_labels(G, pos)
        plt.show()

if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input1') as f:
        print('Example 
        input(f)
        visualize()

if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input2') as f:
        print('Example 
        input(f)
        visualize()

if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input3') as f:
        print('Example 
        input(f)
        visualize()

import sys


def init():
    global inf, mincost
    inf = sys.maxint
    mincost = [inf]*v

def update():
    updated = False
    for i in range(e):
        if mincost[s[i]] is not inf:
            c = mincost[s[i]] + d[i]
            if mincost[t[i]] > c:
                mincost[t[i]] = c
                updated = True
    return updated

def solve():
    init()
    
    mincost[r] = 0
    flag = True
    for i in range(v):
        if not update():
            flag = False
            break
    
    if flag:
        print('NEGATIVE CYCLE')
    else:
        for x in mincost:
            if x is inf:
                print('INF')
            else:
                print(x)

if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input1'

with open(os.environ.get('INPUT') or '/dev/stdin') as f:
    input(f)
    solve()

if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input2'

    with open(os.environ.get('INPUT') or '/dev/stdin') as f:
        input(f)
        solve()

if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input3'

    with open(os.environ.get('INPUT') or '/dev/stdin') as f:
        input(f)
        solve()

Solution (Python):
V,E,r = map(int,input().split())
edges = [tuple(map(int,input().split())) for _ in range(E)]
dist = [float("inf") for _ in range(V)]
dist[r-1] = 0
for i in range(V+1):
    for edge in edges:
        if edge[0] != float("inf") and dist[edge[1]-1] > dist[edge[0]-1]+edge[2]:
            dist[edge[1]-1] = dist[edge[0]-1]+edge[2]
            if i==V-1: print("NEGATIVE CYCLE"); exit()
print("\n".join(str(dist[e-1]) if dist[e-1] != float("inf") else "INF" for e in range(V)))

Solution (Python):



from collections import namedtuple


WEIGHT_MAX = 10 ** 10
WeightedEdge = namedtuple('WeightedEdge', ('src', 'dest', 'weight'))


class Digraph:
    def __init__(self, v):
        self.v = v
        self.edges = [[] for _ in range(v)]

    def add(self, edge):
        self.edges[edge.src].append(edge)

    def adj(self, v):
        return self.edges[v]


def sp_bellmanford(graph, s):
    def relax(edge):
        s, t, w = edge
        if dists[t] > dists[s] + w:
            dists[t] = dists[s] + w
            srcs[t] = s
            _nodes.append(t)

    dists = [WEIGHT_MAX] * graph.v
    dists[s] = 0
    srcs = [-1] * graph.v
    nodes = []

    nodes.append(s)
    for _ in range(graph.v):
        _nodes = []
        for v in nodes:
            for e in graph.adj(v):
                relax(e)
        nodes = _nodes

    if len(nodes) > 0:
        return None
    else:
        return [None if dists[v] == WEIGHT_MAX else dists[v]
                for v in range(graph.v)]


def run():
    v, e, r = [int(i) for i in input().split()]

    graph = Digraph(v)
    for _ in range(e):
        edge = WeightedEdge(*[int(i) for i in input().split()])
        graph.add(edge)

    ws = sp_bellmanford(graph, r)
    if ws is None:
        print("NEGATIVE CYCLE")
    else:
        for w in ws:
            if w is None:
                print("INF")
            else:
                print("{:d}".format(w))


if __name__ == '__main__':
    run()

Solution (Python):
V, E, r = map(int, input().split())
paths = []

for i in range(E) :
    paths.append(list(map(int, input().split())))
    
INF = 10**20

cost = [INF for x in range(V)]
cost[r] = 0

inf_flg = False 

for i in range(V*2) :
    for p in paths :
        f, t, c = p[0], p[1], p[2]

        if cost[t] > cost[f] + c and not(cost[t] == cost[f] == INF):
            cost[t] = cost[f] + c
            
            if i >= V :
                inf_flg = True 
                
if inf_flg == True :
    print("NEGATIVE CYCLE")
else :
    for c in cost :
        if c == INF :
            print("INF")
        else :
            print(c)

Solution (Python):
import sys

inf = sys.maxsize*1000000
V,e,r=(int (i)for i in input().split())
NC=False


G=[]
for j in range(e):
    f,t,cost=(int (i)for i in input().split())
    G.append((f,t,cost))
dist=[inf for _ in range(100000)]

dist[r]=0
max_=0
for i in range(V):
    for (u,v,cost) in G:

        if dist[u]!=inf and dist[u]+cost<dist[v]: 
            if i==V-1:
               
                NC=True
            else:
                dist[v]=dist[u]+cost

        
if not NC:
    for i in range(V):
        if dist[i]>=inf/2:
            print('INF')
        else:
            print(dist[i])
else:
     print("NEGATIVE CYCLE")