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:
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
                    
    #check negative cycle
    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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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


# Even if a negative weight exists, bellman-ford can find shortest paths.
# it also detects negative cycles,
# but not every edges that consist the negative cycles is stored.
# time complexity: O(VE + (V^2))
def bellman_ford(adj, w, s):
    d, parent = initialize_int(adj, s)

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

    # detects negative cycles if exist
    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])

Submission status: Accepted

Solution code:

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 #1')
        input(f)
        visualize()

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

if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input3') as f:
        print('Example #3')
        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()

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
# Edige Weighted Digraph


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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys

inf = sys.maxsize*1000000
V,e,r=(int (i)for i in input().split())
NC=False
#print(v)
#G=[[] for i in range(V)]#iごとに[]（式）を評価(実行)する。
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")

Submission status: Runtime Error

Solution code:
import sys

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: Runtime Error

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

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: Runtime Error

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

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:
        neg = True
        print("NEGATIVE CYCLE")

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

Submission status: Runtime Error

Solution code:
V, E, root = map(int, input().split())
visited = [False] * V
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
    s, t, d = map(int, input().split())
    nodes[s].append(t)
    cost[s].append(d)

dist = [float('inf')] * V
dist[root] = 0

negative_cycle = False

for k in range(V):
    for i in range(V):
        for j in range(nodes[i]):
            if dist[nodes[i][j]] > dist[i] + cost[i][j]:
                dist[nodes[i][j]] = dist[i] + cost[i][j]
                if k==n-1:
                    dist[nodes[i][j]] = -float('inf')
                    negative_cycle = True
if negative_cycle:
    print('NEGATIVE CYCLE')
else:
    for i in range(V):
        if dist[i] == float('inf'):
            print('INF')
        else:
            print(dist[i])

Submission status: Runtime Error

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):
    if dist_lst[v] != INF:
      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):
  if dist_lst[v] != INF:
    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: WA: Presentation Error

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


class Edge(object):
    __slots__ = ('source', 'target', 'cost')

    def __init__(self):
        self.cost = float('inf')
        self.source, self.target = None, None


def generate_edge_table(_v_info):
    for index, each in enumerate(_v_info):
        edge = init_edge_table[index]
        source, target, cost = map(int, each)
        edge.source = source
        edge.target = target
        edge.cost = cost
    return init_edge_table


def bellman_ford():
    distance[root] = 0

    for j in range(vertices - 1):
        for edge in edge_table:
            source, target, cost = edge.source, edge.target, edge.cost
            if distance[source] + cost < distance[target]:
                distance[target] = distance[source] + cost

    for edge in edge_table:
        source, target, cost = edge.source, edge.target, edge.cost
        if distance[source] + cost < distance[target]:
            print('NEGATIVE CYCLE')
            return list()

    return distance


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

    distance = [float('inf')] * vertices
    init_edge_table = tuple(Edge() for _ in range(edges))

    edge_table = generate_edge_table(v_info)

    res = bellman_ford()
    print('\n'.join(('INF' if isinf(ele) else str(ele) for ele in res)))