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: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import collections


G_INF = 2 ** 31


class GraphError(Exception):
    pass


class GraphSearchError(GraphError):

    def __init__(self, reason):
        self.reason = reason

    def __str__(self):
        return str(reason)


class ShortestPathFasterAlgorithm(object):

    def __init__(self, number_of_vertices, adjacency_list, costs, start):
        self.max_v = number_of_vertices
        self.adj = adjacency_list
        self.costs = costs
        self.start = start
        self.dist = None
        self.visits = None

    def initialize(self):
        self.dist = collections.defaultdict(lambda: G_INF)
        self.dist[self.start] = 0
        self.visits = collections.defaultdict(int)

    def single_source_shortest_path(self):
        self.initialize()
        q = collections.deque()
        q.append(self.start)
        while q:
            u = q.popleft()
            self.visits[u] += 1
            if self.visits[u] >= self.max_v:
                raise GraphSearchError("A negative cycle was detected.")
            for v in self.adj[u]:
                new_length = self.dist[u] + self.costs[(u, v)]
                if new_length < self.dist[v]:
                    self.dist[v] = new_length
                    if v not in q:
                        q.append(v)
        return self.dist


def main():
    max_v, max_e, start = map(int, input().split())
    adjacency_list = collections.defaultdict(lambda: array.array("L"))
    costs = collections.defaultdict(lambda: G_INF)
    for _ in range(max_e):
        s, t, d = map(int, input().split())
        adjacency_list[s].append(t)
        costs[(s, t)] = d
    spfa = ShortestPathFasterAlgorithm(max_v, adjacency_list, costs, start)
    try:
        dist = spfa.single_source_shortest_path()
        for v in range(max_v):
            result = dist[v]
            if result < G_INF:
                print(result)
            else:
                print("INF")
    except GraphSearchError as gse:
        print("NEGATIVE CYCLE")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# Input acceptance
import sys

file_input = sys.stdin

V, E, r = map(int, file_input.readline().split())

edges = []

for line in file_input:
    edges.append(tuple(map(int, line.split())))


# Bellman???Ford algorithm
distance = [float("inf")] * V
distance[r] = 0

for i in range(V):
    notUpdated = True
    for e in edges:
        t = e[1]
        temp_d = distance[e[0]] + e[2]
        if temp_d < distance[t]:
            distance[t] = temp_d
            notUpdated = False
    if notUpdated:
        break


# Output
if i == V - 1:
    print("NEGATICE CYCLE")
else:
    print(*map(lambda x: str(x).upper(), distance), sep = '\n')

Submission status: Wrong Answer

Solution code:
# Input acceptance
import sys

file_input = sys.stdin

V, E, r = map(int, file_input.readline().split())

edges = []

for line in file_input:
    edges.append(tuple(map(int, line.split())))


# Bellman???Ford algorithm
distance = [float("inf")] * V
distance[r] = 0

for i in range(V):
    notUpdated = True
    for e in edges:
        t = e[1]
        temp_d = distance[e[0]] + e[2]
        if temp_d < distance[t]:
            distance[t] = temp_d
            notUpdated = False
    if notUpdated:
        break


# Output
if i == V - 1:
    print("NEGATIVE CYCLE")
else:
    print(*map(lambda x: str(x).upper(), distance), sep = '\n')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

output:
INF
0
-5
-3

OR
input:
4 6 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
3 1 0

output:
NEGATIVE CYCLE
"""

import sys
from math import isinf


# WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost

    return init_adj_table


def bellman_ford():
    distance[root] = 0

    for current in range(vertices):
        v_info = adj_table[current].items()
        for adj, cost in v_info:
            if not isinf(distance[current]) and distance[current] + cost < distance[adj]:
                distance[adj] = distance[current] + cost

    for current in range(vertices):
        v_info = adj_table[current].items()
        for adj, cost in v_info:
            if not isinf(distance[current]) and distance[current] + cost < distance[adj]:
                print('NEGATIVE CYCLE')
                return list()

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges, root = map(int, _input[0].split())
    init_vertices_table = map(lambda x: x.split(), _input[1:])
    # assert len(init_vertices_table) == vertices_num

    distance = [float('inf')] * vertices
    # color = [WHITE] * vertices
    init_adj_table = tuple(dict() for _ in range(vertices))

    init_vertex = 0
    adj_table = generate_adj_table(init_vertices_table)

    res = bellman_ford()
    for ele in res:
        if isinf(ele):
            print('INF')
        else:
            print(ele)

Submission status: Wrong Answer

Solution code:
maxd = float('inf')
nv, ne, r = [int(n) for n in input().split(' ')]
vertices = {k: {} for k in range(nv)}
for i in range(ne):
    s, t, w = [int(n) for n in input().split(' ')]
    vertices[s][t] = w

dist = {v: maxd for v in vertices}
dist[r] = 0

for u, targets in vertices.items():
    for v, w in targets.items():
        if dist[v] > dist[u] + w:
            dist[v] = dist[u] + w

for u, targets in vertices.items():
    for v, w in targets.items():
        if dist[v] > dist[u] + w:
            print("NEGATIVE CYCLE")
            exit()

[print(d) if d < maxd else print("INF") for v, d in dist.items()]

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
from sys import stdin

def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    for i in range(V):
        for (u,v) in G.keys():
            if d[v] > d[u] + G[u,v]:
                d[v] = d[u] + G[u,v]
                if i == V:
                    return 'NEGATIVE CYCLE'
    return d


V, E, R = [int(x) for x in stdin.readline().split()]
G = defaultdict()
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split()]
    G[(s,t)] = w
d = sp(G, R, V)
for k in range(V):
    if d == 'NEGATIVE CYCLE':
        print('NEGATIVE CYCLE')
    else:
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

Submission status: Wrong Answer

Solution code:
from sys import stdin



V, E, R = [int(x) for x in stdin.readline().split()]
d = {}
tick = False
INF = float('inf')
for i in range(V):
    d[i] = INF
d[R] = 0
for i in range(1, V+1):
    for case in range(E):
        if i == 1:
            s, t, w = [int(x) for x in stdin.readline().split()]
        if d[t] > d[s] + w:
                d[t] = d[s] + w
                if i == V:
                    print('NEGATIVE CYCLE')
                    tick = True
if not tick:
    for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

Submission status: Wrong Answer

Solution code:
inf = float("inf")

class edge():
    def __init__(self, start, target, cost):
        self.start = start
        self.target = target
        self.cost = cost

def bellman_ford(s):
    d = [inf] * V
    d[s] = 0
    cnt = 0
    updateflag = True
    while True:
        updateflag = False
        for i in es:
            if d[i.start] != inf and d[i.target] > d[i.start] + i.cost:
                d[i.target] = d[i.start] + i.cost
                updateflag = True
        if cnt == V-1: return False
        if not updateflag: break
        cnt += 1
    return d

V,E,r = map(int, input().split())
es = [None] * E
for i in range(E):
    s,t,cost = map(int, input().split())
    es[i] = edge(s, t, cost)
ans = bellman_ford(r)
if ans:
    for i in ans:
        if i == inf: print("INF")
        else: print(i)
else:
   print("NEGATIVE CYCLE")

Submission status: Wrong Answer

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

V, E, r = map(int, readline().split())
inf = 10**10
edges = [[] for _ in [None]*V]

for _ in [None]*E:
    s, t, d = map(int, readline().split())
    edges[s].append((t, d))

vertices = [inf] * V
vertices[r] = 0

for i in range(V):
    flag = 0
    for v in range(V):
        cost = vertices[v]
        for dist, _cost in edges[v]:
            newcost = cost + _cost
            if vertices[dist] > newcost:
                vertices[dist] = newcost
                flag = 1
    if flag == 0:
        for v in vertices:
            print(v if v != inf else "INF")
        break
else:
    print("NEGATIVE CYCLE")

Submission status: Wrong Answer

Solution code:
def main():
    nvertices, nedges, s = map(int, input().split())
    E = []
    for i in range(nedges):
        u, v, w = map(int, input().split())
        E.append((u, v, w))

    INF = 1000000000
    d = [INF] * nvertices
    d[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in E:
            if d[u] + w < d[v]:
                d[v] = d[u] + w

    for i in range(nvertices - 1):
        for u, v, w in E:
            if d[v] > d[u] + w:
                print("NEGATIVE CYCLE")
                return

    for val in d:
        if val >= INF:
            print("INF")
        else:
            print(val)


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

INF = 999999999999999999999
NEGATIVE_CYCLE = -1

def bellman_ford(G, r):
  n = len(G)
  d = {}
  for i in range(n):
    d[i] = INF
  d[r] = 0
  for i in range(n-1):
    d = relax(G, d)
  for u in G:
    for v in G[u]:
      if d[u] + G[u][v] < d[v]:
        return NEGATIVE_CYCLE
  return d

def relax(G, d):
  for u in G:
    if G[u] == INF:
      continue
    for v in G[u]:
      if d[u] + G[u][v] < d[v]:
        d[v] = d[u] + G[u][v]
  return d


G = {}

n, m, r = [int(v) for v in input().strip().split(' ')]
for i in range(n):
  G[i] = {}
for _ in range(m):
  s, t, c = [int(v) for v in input().strip().split(' ')]
  G[s][t] = c

d = bellman_ford(G, r)

if d == NEGATIVE_CYCLE:
  print("NEGATIVE CYCLE")
else:
  for i in range(n):
    if d[i] == INF:
      print("INF")
    else:
      print(d[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

INF = 999999999999999999999
NEGATIVE_CYCLE = -1

def bellman_ford(G, n, r):
  d = {}
  for i in range(n):
    d[i] = INF
  d[r] = 0
  for i in range(n-1):
    d = relax(G, d)
  for u in G:
    for v in G[u]:
      if d[u] + G[u][v] < d[v]:
        return NEGATIVE_CYCLE
  return d

def relax(G, d):
  for u in G:
    if G[u] == INF:
      continue
    for v in G[u]:
      if d[u] + G[u][v] < d[v]:
        d[v] = d[u] + G[u][v]
  return d


G = {}

n, m, r = [int(v) for v in input().strip().split(' ')]
for i in range(n):
  G[i] = {}
for _ in range(m):
  s, t, c = [int(v) for v in input().strip().split(' ')]
  G[s][t] = c

d = bellman_ford(G, n, r)

if d == NEGATIVE_CYCLE:
  print("NEGATIVE CYCLE")
else:
  for i in range(n):
    if d[i] == INF:
      print("INF")
    else:
      print(d[i])

Submission status: Wrong Answer

Solution code:
import sys

INF = float('inf')

def Bellmanford(n, edges, r):
    d = [INF] * n
    d[r] = 0
    
    for i in range(n):
        flag = False
        
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                flag = True
                
        if flag and i == n-1:
            return 'NEGATIVE CYCLE'
        
    d = [di if di < INF else 'INF' for di in d]
    return d

V, E, R = map(int, sys.stdin.readline().split())
Edges = [None] * E

for i in range(E):
    si, ti, di = map(int, sys.stdin.readline().split())
    Edges[i] = (si, ti, di)
    
ans = Bellmanford(V, Edges, R)

print(*ans, sep = '\n')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
INF = float("inf")
V, E, r = inpl()

edges = [inpl() for _ in range(E)]

def belman_ford(V, edges, r):
    "If glaph contains negative cycles then return True"
    D = [INF]*(V)
    D[r] = 0
    
    for _ in range(V-1):
        update = False
        for s, t, d in edges:
            if D[t] > D[s] + d:
                D[t] = D[s] + d
                update = True
        if not update:
            break
    else:
        return True, D
    return False, D
    
NEGATIVE, D = belman_ford(V, edges, r)

if NEGATIVE:
    print("NEGATIVE CYCLE")
else:
    for d in D:
        print("INF") if d == INF else print(d)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 20

v_num, e_num, r = map(int, input().split())
dist_lst = [INF for _ in range(v_num)]
edges_lst = [[] for _ in range(e_num)]
negative_cycle_flag = False

for _ in range(e_num):
  s, t, dist = map(int, input().split())
  edges_lst[s].append((dist, t))

dist_lst[r] = 0

for _ in range(v_num):
  for v in range(v_num):
    for dist, to in edges_lst[v]:
      if dist_lst[v] + dist < dist_lst[to]:
        dist_lst[to] = dist_lst[v] + dist

for v in range(v_num):
  for dist, to in edges_lst[v]:
    if dist_lst[v] + dist < dist_lst[to]:
      negative_cycle_flag = True
      break
  if negative_cycle_flag:
    break

if negative_cycle_flag:
  print("NEGATIVE CYCLE")
else:
  for dist in dist_lst:
    if dist == INF:
      print("INF")
    else:
      print(dist)

Submission status: Wrong Answer

Solution code:
V, E, r = map(int, input().split())

INF = 2 << 21
G = [[] for i in range(V)]
dist = [INF for j in range(V)]


def bellman_ford(s):
    p, flg = [-1 for i in range(V)], [False for i in range(V)]
    dist[s], flg[s], cnt = 0, True, 0

    while True:
        if cnt >= V:
            return False

        on = []
        for i in range(V):
            if flg[i]:
                on.append(i)
                flg[i] = False

        if len(on) == 0:
            return True

        for i in on:
            for j in G[i]:
                if dist[i] + j[1] < dist[j[0]]:
                    dist[j[0]] = dist[i] + j[1]
                    p[j[0]], flg[j[0]] = i, True

        cnt += 1


def main():
    for i in range(E):
        s, t, d = map(int, input().split())
        G[s].append((t, d))

    check = bellman_ford(r)

    if check:
        for i in range(V):
            if dist[i] == INF:
                print("INF")
            else:
                print(dist[i])
    else:
        print("NEGATIVE CYCLE")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
V, E, r = map(int, input().split())

INF = 2 << 21
G, dist = [None for i in range(E)], [INF for j in range(V)]


class Edge:
    def __init__(self, f, t, cost):
        self.f = f
        self.t = t
        self.cost = cost


def bellman_ford(s):
    dist[s] = 0
    for i in range(V):
        for j in range(E):
            e = G[j]
            if dist[e.f] + e.cost < dist[e.t]:
                dist[e.t] = dist[e.f] + e.cost

                if i == V - 1:
                    return True

    return False


def main():
    for i in range(E):
        s, t, d = map(int, input().split())
        G[i] = Edge(s, t, d)

    c = bellman_ford(r)

    if c:
        print("NEGATIVE CYCLE")
    else:
        for i in range(V):
            if dist[i] == INF:
                print("INF")
            else:
                print(dist[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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 'NegativeCycle'
            
            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

    
V, E, S = list(map(int, input().split()))
bf = BellmanFord(V)
for i in range(E):
    frm, to, cost = list(map(int, input().split()))
    bf.add_edge(frm, to, cost)
    

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

Submission status: Accepted

Solution code:
V, E, r = map(int, input().split())
nodes = [list(map(int, input().split())) for _ in range(E)] #e = from, to, cost

def shortest_path(s):
    d = [float('inf') for i in range(V)]
    d[s] = 0
    for _ in range(V):
        update = False
        for i in range(E):
            e = nodes[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 update:
        return None
    else:
        return d

if not shortest_path(r):
    print('NEGATIVE CYCLE')
else:
    d = shortest_path(r)
    for i in range(V):
        if d[i] == float('inf'):
            print('INF')
        else:
            print(d[i])

Submission status: Accepted

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

import sys

sys.setrecursionlimit(10 ** 9)
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()))
INF=float('inf')

# ベルマンフォード(頂点数, 辺集合(0-indexed), 始点)
def bellman_ford(N: int, edges: list, src: int) -> list:
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for i in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for src, dest, cost in edges:
        if res[dest] > res[src] + cost:
            # あったら空リストを返却
            return []
    # 問題なければ頂点リストを返却
    return res

N,M,r=MAP()
edges=[None]*M
for i in range(M):
    s,t,d=MAP()
    edges[i]=(s, t, d)

ans=bellman_ford(N, edges, r)

if not len(ans):
    print('NEGATIVE CYCLE')
    exit()

for i in range(N):
    if ans[i]==INF:
        ans[i]='INF'
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys

inf = int(1e12)

def shortestPath(graph, s):
    n = len(graph)
    dist = [inf for _ in range(n)]
    dist[s] = 0

    for i in range(n):
        for u in range(n):
            for v, cost in graph[u]:
                newDist = dist[u] + cost
                if dist[u] != inf and newDist < dist[v]:
                    if i == n - 1:
                        return None
                    dist[v] = newDist
    return dist

def main():
    v, e, s = map(int, input().split())
    
    graph = [[] for _ in range(v)]
    
    for i in range(e):
        a, b, cost = map(int, input().split())
        graph[a].append((b, cost))
            
    dist = shortestPath(graph, s)

    if not dist:
        print("NEGATIVE CYCLE")
    else:
        for d in dist:
            if d >= inf:
                print("INF")
            else:
                print(d)
main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop


def bellman_ford(V, Edges, start):
    dis = {}
    
    for i in range(V): dis[i] = (1 << 30)
    
    dis[start] = 0
    
    for i in range(V):
        for a, b, w in Edges:
            if dis[a] != (1 << 30) and dis[a] + w < dis[b]:
                dis[b] = dis[a] + w
    
    for a, b, w in Edges:
        if dis[a] != (1 << 30) and dis[a] + w < dis[b]:
            return ('NEGATIVE CYCLE', dis)
    
    return ('No NEGATIVE CYCLE', dis)
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    V, E, start = line.split()
    V, E, start = int(V), int(E), int(start)
    Es = []
    for i in range(E):
        line = sys.stdin.readline()
        a, b, w = line.split()
        a, b, w = int(a), int(b), int(w)
        Es.append((a,b,w))
        
    judge, dis = bellman_ford(V, Es, start)
    
    if judge == 'NEGATIVE CYCLE':
        sys.stdout.write(judge + '\n')
    else:
        for i in range(V):
            if dis[i] == (1 << 30):
                sys.stdout.write('INF\n')
            else:
                sys.stdout.write(str(dis[i]) + '\n')

Submission status: Accepted

Solution code:
class exist_negative_cycle(Exception):
    pass
def bellman_ford(g, size, start=0):
    d = [float('inf')] * size
    d[start] = 0
   
    for _ in range(size):
        for u in g:
            for length, v in g[u]:
                if d[v] > d[u] + length:
                    d[v] = d[u] + length

    for u in g:
        for length, v in g[u]:
            if d[v] > d[u] + length:
                raise exist_negative_cycle    
    return d
from sys import stdin
readline = stdin.readline
import math
from collections import defaultdict

vertex, edge, r = map(int, readline().split())

g = defaultdict(list)
for i in range(edge):
    s, t, length = map(int, readline().split())
    g[s].append((length, t))
try:
    d = bellman_ford(g, vertex, r)
    for di in d:
        print('INF' if math.isinf(di) else di)
except exist_negative_cycle:
    print('NEGATIVE CYCLE')

Submission status: Accepted

Solution code:
def bellman_ford(vertices, edges, source):
    for v in vertices:
        if v is source:
            v.distance = 0
        else:
            v.distance = Infinity()
        v.predecessor = None
    for _ in xrange(len(vertices)-1):
        for uv in edges:
            u = uv.source
            v = uv.destination
            if v.distance > u.distance + uv.weight:
                v.distance = u.distance + uv.weight
                v.predecessor = u
    for uv in edges:
        u = uv.source
        v = uv.destination
        if u.distance + uv.weight < v.distance:
            raise NegativeCycleError

def main():
    V, E, r = map(int, raw_input().split())
    vertices = [Vertex() for _ in xrange(V)]
    edges = []
    for _ in xrange(E):
        s, t, d = map(int, raw_input().split())
        edges.append(Edge(vertices[s], vertices[t], d))
    try:
        bellman_ford(vertices, edges, vertices[r])
        for v in vertices:
            print v.distance
    except NegativeCycleError:
        print "NEGATIVE CYCLE"

class Infinity(object):
    def __eq__(self, other):
        return other is self

    def __lt__(self, other):
        return False

    def __gt__(self, other):
        return True

    def __add__(self, other):
        return self

    def __radd__(self, other):
        return slef

    def __str__(self):
        return "INF"
    __repr__ = __str__

class NegativeCycleError(Exception):
    pass

class Edge(object):
    def __init__(self, source, destination, weight):
        self.source = source
        self.destination = destination
        self.weight = weight

class Vertex(object):
    def __init__(self, distance=None, predecessor=None):
        self.distance = distance
        self.predecessor = predecessor

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def bellman_ford(vertices, edges, source):
    for v in vertices:
        if v is source:
            v.distance = 0
        else:
            v.distance = Infinity()
        v.predecessor = None
    for _ in xrange(len(vertices)-1):
        for uv in edges:
            u = uv.source
            v = uv.destination
            if v.distance > u.distance + uv.weight:
                v.distance = u.distance + uv.weight
                v.predecessor = u
    for uv in edges:
        u = uv.source
        v = uv.destination
        if u.distance + uv.weight < v.distance:
            raise NegativeCycleError

def main():
    V, E, r = map(int, raw_input().split())
    vertices = [Vertex() for _ in xrange(V)]
    edges = []
    for _ in xrange(E):
        s, t, d = map(int, raw_input().split())
        edges.append(Edge(vertices[s], vertices[t], d))
    try:
        bellman_ford(vertices, edges, vertices[r])
        for v in vertices:
            print v.distance
    except NegativeCycleError:
        print "NEGATIVE CYCLE"

class Infinity(object):
    def __eq__(self, other):
        return other is self

    def __lt__(self, other):
        return False

    def __gt__(self, other):
        return True

    def __add__(self, other):
        return self

    def __radd__(self, other):
        return self

    def __str__(self):
        return "INF"
    __repr__ = __str__

class NegativeCycleError(Exception):
    pass

class Edge(object):
    def __init__(self, source, destination, weight):
        self.source = source
        self.destination = destination
        self.weight = weight

class Vertex(object):
    def __init__(self, distance=None, predecessor=None):
        self.distance = distance
        self.predecessor = predecessor

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class BellmanFord:
    """Bellman-Ford algorithm : find the shortest path from a vertex
       Complexity: O(VE)
       used in GRL1A(AOJ)
    """

    def __init__(self, V, E, start, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (all edge in E must be 0 or positive)
            start: start vertex
            INF: Infinity distance
        """
        self.V = V
        self.E = E
        self.bellman_ford(start, INF)

    def bellman_ford(self, start, INF):
        self.distance = [INF] * self.V # distance from start
        self.prev = [-1] * self.V # prev vertex of shortest path
        self.distance[start] = 0
        self.negativeCycle = False
        
        for i in range(V):
            update = False
            for v in range(V):
                for to, cost in self.E[v]:
                    if self.distance[v] != INF and self.distance[v] + cost < self.distance[to]:
                        self.distance[to] = self.distance[v] + cost
                        self.prev[to] = v
                        update = True
                        if i == V - 1:
                            self.negativeCycle = True
            if update == False:
                break

    def getPath(self, end):
        assert self.hasNegativeCycle() == False
        path = [end]
        while self.prev[end] != -1:
            end = self.prev[end]
        return path[::-1]

    def hasNegativeCycle(self):
        return self.negativeCycle

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

sp = BellmanFord(V, edge, r, INF)
if sp.hasNegativeCycle():
    print('NEGATIVE CYCLE')
else:
    print(*[dist if dist != INF else 'INF' for dist in sp.distance], sep='\n')

Submission status: Accepted

Solution code:
class BellmanFord:
    """Bellman-Ford algorithm : find the shortest path from a vertex
       Complexity: O(VE)
       used in GRL1A(AOJ)
    """

    def __init__(self, V, E, start, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (all edge in E must be 0 or positive)
            start: start vertex
            INF: Infinity distance
        """
        self.V = V
        self.E = E
        self.bellman_ford(start, INF)

    def bellman_ford(self, start, INF):
        self.distance = [INF] * self.V # distance from start
        self.prev = [-1] * self.V # prev vertex of shortest path
        self.distance[start] = 0
        self.negativeCycle = False
        
        for i in range(V):
            update = False
            for v in range(V):
                for to, cost in self.E[v]:
                    if self.distance[v] != INF and self.distance[v] + cost < self.distance[to]:
                        self.distance[to] = self.distance[v] + cost
                        self.prev[to] = v
                        update = True
                        if i == V - 1:
                            self.negativeCycle = True
            if update == False:
                break

    def getPath(self, end):
        assert self.hasNegativeCycle() == False
        path = [end]
        while self.prev[end] != -1:
            end = self.prev[end]
        return path[::-1]

    def hasNegativeCycle(self):
        return self.negativeCycle

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

sp = BellmanFord(V, edge, r, INF)
if sp.hasNegativeCycle():
    print('NEGATIVE CYCLE')
else:
    for dist in sp.distance:
        print(dist if dist != INF else 'INF')

Submission status: Accepted

Solution code:
inf = float("inf")
def bellman_ford(es, s):
    d[s] = 0
    for cnt in xrange(V):
        update = False
        for e in es:
            frm, to, cost = e
            if d[frm] != inf and d[to] > d[frm] + cost:
                d[to] = d[frm] + cost
                update = True
                if cnt == i - 1:
                    return True
    return False

V, E, r = map(int, raw_input().split())
es = [map(int, raw_input().split()) for i in xrange(E)]
d = [inf for i in xrange(V)]
negative = bellman_ford(es, r)
if negative:
    print "NEGATIVE CYCLE"
else:
    for i in d:
        if i < inf:
            print i
        else:
            print "INF"

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from math import isinf


def main():
    V, E, r = map(int, input().split())
    vertices = [float('inf')] * V
    vertices[r] = 0
    edges = []
    for i in range(E):
        s, t, d = map(int, input().split())
        edges.append((s, t, d))

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

    for s, t, d in edges:
        if vertices[t] > vertices[s] + d:
            print("NEGATIVE CYCLE")
            return

    for v in vertices:
        print('INF' if isinf(v) else v)

main()