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
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]
        if cost == inf:
            continue
        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: Accepted

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


def bellman_ford(n, edges, start):
    vertices = [inf] * n
    vertices[start] = 0
    reached = {start}

    for i in range(n):
        flag = 0
        for v in reached.copy():
            cost = vertices[v]
            for dist, _cost in edges[v]:
                newcost = cost + _cost
                if vertices[dist] > newcost:
                    vertices[dist] = newcost
                    reached.add(dist)
                    flag = 1
        if flag == 0:
            return vertices
    else:
        return None

result = bellman_ford(V, edges, r)
if result:
    print("\n".join([str(n) if n!=inf else "INF" for n in result]))
else:
    print("NEGATIVE CYCLE")

Submission status: Accepted

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] == INF:
                continue
            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] == INF:
                continue
            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: Accepted

Solution code:
import math


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 = float('inf')
    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 math.isinf(val):
            print("INF")
        else:
            print(val)


main()

Submission status: Accepted

Solution code:
import math


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 = float('inf')
    weights = [INF] * nvertices
    weights[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in E:
            if weights[v] > weights[u] + w:
                weights[v] = weights[u] + w
    for u, v, w in E:
        if weights[v] > weights[u] + w:
            print("NEGATIVE CYCLE")
            return

    for w in weights:
        if math.isinf(w):
            print("INF")
        else:
            print(w)


main()

Submission status: Accepted

Solution code:
import math


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

    INF = float('inf')
    weights = [INF] * nvertices
    weights[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in edges:
            if weights[v] > weights[u] + w:
                weights[v] = weights[u] + w

    for u, v, w in edges:
        if weights[v] > weights[u] + w:
            print("NEGATIVE CYCLE")
            return

    for w in weights:
        if math.isinf(w):
            print("INF")
        else:
            print(w)


main()

Submission status: Accepted

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] == INF and d[v] == INF:
        continue
      if d[u] + G[u][v] < d[v]:
        return NEGATIVE_CYCLE
  return d

def relax(G, d):
  for u in G:
    if d[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: Accepted

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

    INF = float('inf')
    weights = [INF] * nvertices
    weights[s] = 0
    for i in range(nvertices - 1):
        for u, v, w in edges:
            if weights[v] > weights[u] + w:
                weights[v] = weights[u] + w

    for u, v, w in edges:
        if weights[v] > weights[u] + w:
            print("NEGATIVE CYCLE")
            return

    for w in weights:
        print(w if w < INF else 'INF')


main()

Submission status: Accepted

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: Accepted

Solution code:
import sys

INF = float('inf')

def Bellmanford(n, edges, r): #r: ?§????
    d = [INF] * n
    d[r] = 0
    
    for i in range(n):
        
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if 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: Accepted

Solution code:
from collections import defaultdict
v_num, e_num, source = (int(n) for n in input().split(" "))
conn = []
cost = [float("inf") for n in range(v_num)]
cost[source] = 0
for _ in range(e_num):
    s1, t1, weight = (int(n) for n in input().split(" "))
    conn.append([s1, t1, weight])

def bellman_ford(source, conn, v_num, cost):
    for i in range(v_num):
        for s, t, weight in conn:
            if cost[t] > cost[s] + weight:
                if i == v_num - 1:
                    return True
                cost[t] = cost[s] + weight
    return False

if bellman_ford(source, conn, v_num, cost):
    print("NEGATIVE CYCLE")
else:
    cost = ["INF" if n == float("inf") else n for n in cost]
    for c in cost:
        print(c)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=jp

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline


def shortest_path(es, V, s):
    count = 0
    d = [float('inf')] * V
    d[s] = 0

    while True:
        update = False
        count += 1

        if count > V:
            return None

        for e in es:
            if d[e.f] != float('inf') and d[e.t] > d[e.f] + e.c:
                d[e.t] = d[e.f] + e.c
                update = True
        if update is False:
            break

    for i, dist in enumerate(d):
        if dist == float('inf'):
            d[i] = 'INF'
    return d


edge = namedtuple('edge', ['f', 't', 'c'])
def main(args):
    V, E, r = map(int, input().split())
    es = []
    for _ in range(E):
        s, t, d = map(int, input().split())
        es.append(edge(s, t, d))

    result = shortest_path(es, V, r)

    if result is None:
        print('NEGATIVE CYCLE')
    else:
        print('\n'.join(map(str, result)))


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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
    if V == 1:
        return False, [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: Accepted

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):
    D = [INF]*(V)
    D[r] = 0
    if V == 1:
        return [0], [False]
    
    for _ in range(V):
        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:
        NEGATIVE = [False]*(V)
        for s, t, d in edges:
            if D[t] > D[s] + d:
                D[t] = D[s] + d
                NEGATIVE[t] = True
                NEGATIVE[s] = True
        return D, NEGATIVE
                
    return D, [False]*(V)
    
D, NEGATIVE = belman_ford(V, edges, r)

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

Submission status: Accepted

Solution code:
import queue


class Edge:
    def __init__(self, _to, _cost):
        self.to = _to
        self.cost = _cost


def bellman(n, graph, start):
    dist = [0 if i == start else float('inf') for i in range(n)]

    for i in range(n):
        for v in range(n):
            for e in graph[v]:
                if dist[v] == float('inf') or dist[e.to] <= dist[v] + e.cost:
                    continue

                dist[e.to] = dist[v] + e.cost

                if i == n - 1:
                    return None

    return dist


def main():
    n, m, s = map(int, input().split())
    graph = [[] for _ in range(n)]

    for _ in range(m):
        data = list(map(int, input().split()))

        graph[data[0]].append(Edge(data[1], data[2]))

    ans = bellman(n, graph, s)

    if ans is None:
        print("NEGATIVE CYCLE")
    else:
        for i in range(n):
            print(ans[i] if ans[i] != float('inf') else "INF")
        return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
v, e, r = map(int, input().split())
a = []
for i in range(e):
    A = list(map(int, input().split()))
    a.append(A)

costs = [None] * v
costs[r] = 0
count = 0
while True:
    count += 1
    update = False
    for s, t, d in a:
        if costs[s] is None:
            continue
        cost = costs[s] + d
        if costs[t] is None or costs[t] > cost:
            costs[t] = cost
            update = True
    if not update:
        for cost in costs:
            print("INF" if cost is None else cost)
        break
    if count == v:
        print("NEGATIVE CYCLE")
        break

Submission status: Accepted

Solution code:
"""
BellmanFord
"""

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

if e_num != 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: Accepted

Solution code:
d = []          # コスト distance

# input
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:
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 >= 2 * 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: Accepted

Solution code:
from collections import deque

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, q1 = [-1 for i in range(V)], deque()
    dist[s], cnt = 0, 0
    q1.append(s)

    while True:
        if cnt >= 2 * V:
            return False

        if len(q1) == 0:
            return True

        q2 = deque()
        for i in q1:
            for j in G[i]:
                if dist[i] + j[1] < dist[j[0]]:
                    dist[j[0]], p[j[0]] = dist[i] + j[1], i
                    q2.append(j[0])

        q1 = q2
        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: Accepted

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] < INF and 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:
n,m,r=map(int,input().split())
a,b,c=[0]*m,[0]*m,[0]*m
INF=10**18
for i in range(m):
  a[i],b[i],c[i]=map(int,input().split())
d=[INF]*n
d[r]=0
for _ in range(n-1):
  for i in range(m):
    if d[a[i]]==INF:continue
    d[b[i]]=min(d[b[i]],d[a[i]]+c[i])
for _ in range(n):
  for i in range(m):
    if d[a[i]]==INF:continue
    if d[b[i]]>d[a[i]]+c[i]:
      print('NEGATIVE CYCLE')
      exit()
for i in d:
  print([i,'INF'][i==INF])

Submission status: Accepted

Solution code:
def bellman_ford(vertexes, edges, costs, start):
    # cost to each vertex
    d = [float("inf")] * vertexes
    # start cost is zero
    d[start] = 0
    for i in range(vertexes):
        update = False
        for j in range(len(edges)):
            frm, to = edges[j]
            cost = costs[j]
            if d[to] > d[frm] + cost:
                d[to] = d[frm] + cost
                update = True
        # stop if not updated
        if not update:
            break

        # find if closed-loop exists
        if i == n - 1:
            return -1

    return d


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

edges = []
costs = [-float("inf")] * (m)
score = [-float("inf")] * (n + 1)

for i in range(m):
    a, b, c = map(int, input().split())
    edges.append([a, b])
    costs[i] = c

d = bellman_ford(n, edges, costs, s)

if d == -1:
    print("NEGATIVE CYCLE")
else:
    for i in range(n):
        print(d[i]) if d[i] != float("inf") else print("INF")

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

class BellmanFord:
    def __init__(self, n):
        self.N = n
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append((v,d))

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]

    def search(self, s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        update = True
        cnt = 0
        while update:
            cnt += 1
            if cnt > self.N:
                return d,True
            update = False
            for k,v in self.e.items():
                if d[k] == inf:
                    continue
                dk = d[k]
                for n,nd in v:
                    if d[n] > dk + nd:
                        update = True
                        d[n] = dk + nd

        return d,False

    # 繝｡繧ｽ繝・ラ縺ｮ縺ｿ迚・
    def search(s, N):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        update = True
        cnt = 0
        while update:
            cnt += 1
            if cnt > N:
                return d,True
            update = False
            for k,v in e.items():
                if d[k] == inf:
                    continue
                dk = d[k]
                for n,nd in v:
                    if d[n] > dk + nd:
                        update = True
                        d[n] = dk + nd

        return d,False


def main():
    v,e,r = LI()
    std = [LI() for _ in range(e)]

    e = collections.defaultdict(list)
    for s,t,d in std:
        e[s].append((t,d))

    def search(s, N):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        us = set([s])
        cnt = 0
        while us:
            cnt += 1
            if cnt > N:
                return d,True
            ns = set()
            for k,v in e.items():
                if d[k] == inf:
                    continue
                dk = d[k]
                for n,nd in v:
                    if d[n] > dk + nd:
                        ns.add(n)
                        d[n] = dk + nd
            us = ns

        return d,False

    d,f = search(r,v)
    if f:
        return "NEGATIVE CYCLE"

    r = []
    for i in range(v):
        t = d[i]
        if t == inf:
            r.append("INF")
        else:
            r.append(t)


    return JA(r, "\n")

print(main())

Submission status: Accepted

Solution code:
# Bellman-Ford Algorithm

def bellman_ford(s):
    '''
    始点sから各頂点への最短距離を求める (重み付き有向グラフ)
    '''
    dist = [float('inf')] * v
    dist[s] = 0

    for i in range(v):
        update = False
        for p, q, cost in edge:
            if dist[p] != float('inf') and dist[q] > dist[p] + cost:
                dist[q] = dist[p] + cost
                update = True
        if not update:
            break
        if i == v - 1:  # 負閉路が存在する場合はFalseを返す
            return False

    return dist


################################
v, e, r = map(int, input().split())  # v:頂点数, e:辺の数

edge = []  # edge[i]:[始点,終点,重み]
for _ in range(e):
    s, t, d = map(int, input().split())
    edge.append([s, t, d])

res = bellman_ford(r)

if not res:
    print('NEGATIVE CYCLE')
else:
    for v in res:
        if v == float('inf'):
            print('INF')
        else:
            print(v)

Submission status: Accepted

Solution code:
# グラフクラスとベルマンフォードクラスの定義
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for i in range(n+1)]

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n + 1) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class Graph():
    def __init__(self, N, Type):
        self._V = N  # 頂点の数
        self._E = 0  # 辺の数
        self.type = Type
        if Type == "D":
            # 2次元リスト
            self.G = [[] for i in range(self._V+1)]
        elif Type == "W":
            # 隣接行列
            self.G = [[float("inf") for i in range(self._V+1)]
                      for j in range(self._V+1)]
        elif Type == "B" or Type == "K":
            # 1次元リスト
            self.G = []

    def E(self):
        """ 辺数 """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self._E += 1
        if self.type == "D":
            self.G[_from].append((_to, _cost))

        elif self.type == "W":
            self.G[_from][_to] = _cost

        elif self.type == "B" or self.type == "K":
            self.G.append((_from, _to, _cost))

    def add_both(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する (無向グラフ) """
        self.add(_from, _to, _cost)
        self.add(_to, _from, _cost)


class Bellman_Ford(Graph):
    def __init__(self, N):
        super().__init__(N, "B")
        self.d = [float("inf")]*(self._V+1)

    def shortest_path(self, s):
        self.d[s] = 0
        for _ in range(self._V):
            flag = False
            for From, To, cost in self.G:
                newlen = self.d[From]+cost
                if newlen < self.d[To]:
                    flag = True
                    self.d[To] = newlen
            if not flag:
                break
        return self.d

    def have_negative_circle(self, s):
        self.d[s] = 0
        for i in range(1, self._V+1):
            flag = False
            for From, To, cost in self.G:
                newlen = self.d[From]+cost
                if newlen < self.d[To]:
                    flag = True
                    self.d[To] = newlen
            if not flag:
                break
            if i == self._V:
                return False
        return self.d


def main():
    V, E, r = map(int, input().split())
    r+=1
    # ベルマンフォードクラスのインスタンスを定義
    G = Bellman_Ford(V)
    for i in range(E):
        s, t, d = map(int, input().split())
        s+=1
        t+=1
        G.add(s,t,d)
    result = G.have_negative_circle(r)
    if result==False:
        print("NEGATIVE CYCLE")
        return
    else:
        for i in range(1, V+1):
            if result[i] == float("inf"):
                print("INF")
            else:
                print(result[i])
        return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF = 10 ** 18
n, m, r = map(int, input().split())
d = [INF] * n
d[r] = 0
p = [False] * n
p[r] = True
e = [None] * m
for i in range(m):
    e[i] = tuple(map(int, input().split()))
for _ in range(n):
    flg = 1
    for s, t, da in e:
        if p[s] == True and d[t] > d[s] + da:
            d[t] = d[s] + da
            p[t] = True
            flg = 0
    if flg:
        break
else:
    print('NEGATIVE CYCLE')
    exit(0)
for x in d:
    if x >= 10 ** 10:
        print('INF')
    else:
        print(x)

Submission status: Accepted

Solution code:
v, e, r = map(int, input().split())
edges = []
for _ in range(e):
    s, t, d = map(int, input().split())
    edges.append((s, t, d))

def shortest_path(v, s, edges, inf):
    d = [inf] * v
    d[s] = 0
    cnt = 0
    while True:
        cnt += 1
        update = False
        for frm, to, cost in edges:
            if d[frm] != inf and d[to] > d[frm] + cost:
                d[to] = d[frm] + cost
                update = True
        if cnt == v and update:
            return False
        elif not update:
            break
    return d

inf = 10 ** 9
d = shortest_path(v, r, edges, inf)
if d == False:
    print('NEGATIVE CYCLE')
else:
    for i in range(v):
        if d[i] == inf:
            print('INF')
        else:
            print(d[i])

Submission status: Accepted

Solution code:
V,E,r = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(E)]
dp = [float("INF")]*(V)
dp[r] = 0
cnt = 0
while True:
    cnt += 1
    if cnt > V:
        print("NEGATIVE CYCLE")
        exit()
    flag = False
    for s,t,d in edges:
        if dp[t] > dp[s]+d:
            dp[t] = dp[s]+d
            flag = True
    if not flag:
        break
for c in dp:
    if c == float("INF"):
        print("INF")
    else:
        print(c)

Submission status: Accepted

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

dd[r]=0 
for i in range(V-1):
    update=0 
    for s,t,d in g:
        if dd[t]> dd[s]+d and dd[s]!= inf:
            dd[t]= dd[s]+d
            update+=1
    if update==0: 
        break

update= False
for s,t,d in g:
    if dd[t]> dd[s]+d and dd[s]!=inf:
        update=True
        break

if update:
    print("NEGATIVE CYCLE")
else:
    for i in dd:
        if i==inf:
            print("INF")
        else:
            print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def beruman(N,edges,start = 0,negative_loop = False):
    find_negative = False #startを含む負の閉路が存在するか
    dist = [INF] * N
    dist[start] = 0

    for i in range(N):
        update = False
        for a,b,c in edges:
            if dist[a] != INF and dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                update = True

        if not update:
            break
        if i == N - 1:
            find_negative = True
    
    if negative_loop:
        return dist,find_negative
    else:
        return dist

def main():
	V,E,s = map(int,input().split())
	edges = [tuple(map(int,input().split())) for _ in range(E)]
	dist,flag = beruman(V,edges,start = s,negative_loop = True) 
	if flag:
		print('NEGATIVE CYCLE')
	else:
		print('\n'.join(map(lambda x:'INF' if x == INF else str(x),dist)))
if __name__ == '__main__':
	main()