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


Verified:
    https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_B
"""
from typing import List, Optional, Tuple


def bellman_ford(
    source: int, vertices_count: int, edges: List[Tuple]
) -> Optional[List[float]]:
    """Bellman-Ford algorithm: O(NM)
    Compute the distance of the shortest path from V_source to each vertex.
    Relax edges in N-1 times of loops and detect negative cycles in the last loop.

    Args:
        source: V_source
        edges: Edges info
        vertices_count: Number of vertices
    Returns:
        Return None if the graph has negative cycles.
        If not, return a list of distance from V_source.
    """
    inf = float("inf")
    dist = [inf] * (vertices_count + 1)
    dist[source] = 0
    for i in range(vertices_count):
        for from_, to, weight in edges:
            if dist[from_] + weight < dist[to]:
                dist[to] = dist[from_] + weight
                if i == vertices_count - 1:
                    return None
    return dist


def main():
    V, E, R, *edges = map(int, open(0).read().split())
    dist = bellman_ford(R, V, list(zip(*[iter(edges)] * 3)))
    inf = float("inf")
    if dist:
        print("\n".join(map(str, (i if i != inf else "INF" for i in dist[:-1]))))
    else:
        print("NEGATIVE CYCLE")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from heapq import heappop, heappush
    INF = 1 << 30

    n, m, r, *E = map(int, open(0).read().split())

    G = [[] for _ in [0]*n]
    for s, t, w in zip(*[iter(E)]*3):
        G[s].append((t, w))

    # Shortest Path Faster Algorithm (SPFA)
    D = [INF]*n
    count = [0]*n
    in_queue = [False]*n
    q = []
    
    D[r] = 0
    count[r] = 1
    in_queue[r] = True
    heappush(q, (0, r))

    while q:
        _, s = heappop(q)
        in_queue[s] = False

        for t, w in G[s]:
            new_d = D[s] + w
            if new_d >= D[t]:
                continue
            D[t] = new_d

            count[t] += 1
            if count[t] >= n:
                print('NEGATIVE CYCLE')
                exit()

            if not in_queue[t]:
                in_queue[t] = True
                heappush(q, (new_d, t))

    print(*['INF' if d == INF else d for d in D], sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from collections import defaultdict

def resolve():
    it = map(int, sys.stdin.read().split())
    V, E, r = next(it), next(it), next(it)

    inf = float("inf")

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

    dx = defaultdict(list)
    for si, ti, di in zip(it, it, it):
        dx[si].append((ti, di))

    sx, tx = {r,}, set()
    for i in range(V+1):
        if not sx: break
        for si in sx:
            for ti, di in dx[si]:
                d1 = dp[ti]
                d2 = dp[si] + di
                if d1 > d2:
                    dp[ti] = d2
                    tx.add(ti)
        sx, tx = tx, set()

    if sx:
        print("NEGATIVE CYCLE")
        return

    ans = []
    print(*["INF" if x == inf else x for x in dp], sep="\n")



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
class Edge():
    def __init__(self, src, to, weight):
        self.src = src
        self.to = to
        self.weight = weight

class NegativeWeightDirectedGraph():
    def __init__(self, V):
        self.V = V
        self.Edges = []
        self.INF = 10**10

    def append(self, src, to, weight):
        self.Edges.append(Edge(src, to, weight))

    def bellmanFord(self, s):
        D = [self.INF] * self.V
        D[s] = 0
        for _ in range(self.V-1):
            for e in self.Edges:
                if D[e.src] != self.INF:
                    w = D[e.src] + e.weight
                    D[e.to] = min(D[e.to], w)
        # check
        for e in self.Edges:
            if D[e.src] == self.INF:
                continue
            if D[e.src] + e.weight < D[e.to]:
                return None
        return D


V,E,r = map(int, raw_input().split())
G = NegativeWeightDirectedGraph(V)
for i in range(E):
    s,t,d = map(int, raw_input().split())
    G.append(s,t,d)

ans = G.bellmanFord(r)
if ans == None:
    print "NEGATIVE CYCLE"
else:
    for d in ans:
        if d == G.INF:
            print "INF"
        else:
            print d

Submission status: Accepted

Solution code:
def solve(V,E,r,edges):
    cost=[float('inf')]*V
    cost[r]=0
    for _ in range(V-1):
        for edge in edges:
            s=edge[0]
            t=edge[1]
            d=edge[2]
            if cost[t]>cost[s]+d:
                cost[t]=cost[s]+d
    for edge in edges:
        s=edge[0]
        t=edge[1]
        d=edge[2]
        if cost[t]>cost[s]+d:
            return []
    return cost
            
V,E,r=map(int,input().split())
edges=[]
for _ in range(E):
    s,t,d=map(int,input().split())
    edges.append(tuple((s,t,d)))
ans=solve(V,E,r,edges)
if len(ans)==0:
    print("NEGATIVE CYCLE")
else:
    for i in range(len(ans)):
        if ans[i]==float('inf'):
            print("INF")
        else:
            print(ans[i])

Submission status: Accepted

Solution code:
v,e,r=map(int,input().split())
d=[float("INF")]*v
edges=[[] for i in range(v)]
for i in range(e):
    a,*s=map(int,input().split())
    edges[a].append(s)
d[r]=0
from collections import deque

#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i in range(v+2):
    f=False
    used=set()
    dq=deque([r])
    while dq:
        a=dq.popleft()
        for to,c in edges[a]:
            if d[to]>c+d[a]:
                f=True
                d[to]=c+d[a]
            if to not in used:dq.append(to);used.add(to)
    if i==v:print("NEGATIVE CYCLE");exit()
    if f:continue
    break
for i in d:
    print("INF" if i==float("INF") else i)

Submission status: Accepted

Solution code:
v, e, r = map(int, input().split())
g = [[] for _ in range(v)]
for i in range(e):
    s, t, d = map(int, input().split())
    g[s].append((d, t))#(重み, 次の頂点)

dist = [float("inf")] * v
dist[r] = 0
updated = False

for k in range(v-1):
    updated = False

    for i in range(v):
        for j in g[i]:
            if dist[i] != float("inf") and dist[i] + j[0] < dist[j[1]]:
                dist[j[1]] = dist[i] + j[0]
                updated = True
    if not updated:
        break
if updated:
    print("NEGATIVE CYCLE")
    exit()

for i in dist:
    if i == float("inf"):
        print("INF")
    else:
        print(i)

Submission status: Accepted

Solution code:
V,E,r = map(int,input().split())
# adj_list = [ [] for _ in range(V)]
INF = float('inf')
edges = []

for _ in range(E):
  s,d,c = map(int, input().split())
  edges.append([s,d,c])


dist = [INF] * V
dist[r] = 0
for _ in range(V-1):
  for s,d,c in edges:
    # import pdb; pdb.set_trace()
    if dist[d] > dist[s] + c:
      dist[d] = dist[s] + c

for s,d,c in edges:
  if dist[d] > dist[s] + c:
    print("NEGATIVE CYCLE")
    exit()

for d in dist:
  print(d if d!=INF else "INF")

Submission status: Accepted

Solution code:
INF = float("inf")


def bellman_ford(edges, num_v, sv):
    #グラフの初期化
    dist = [INF for i in range(num_v)]
    dist[sv]=0
    
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            s, t, d = edge[0], edge[1], edge[2]
            if dist[s] != INF and dist[t] > dist[s] + d:
                dist[t] = dist[s] + d
                if i == num_v - 1:
                    return -1       # 負の閉路が存在する
    
    return dist


def main():
    N, M, r = map(int, input().split())

    edges = []
    for _ in range(M):
        s, t, d = map(int, input().split())
        edges.append([s, t, d])
    
    dist = bellman_ford(edges, N, r)
    if dist == -1:
        print("NEGATIVE CYCLE")
    else:
        for i in range(N):
            ans = dist[i]
            if ans == INF:
                ans = "INF"
            print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,collections
N,E,r = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
sdw = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) # multi line with multi param
#sdw = [[src1 dist1 d1][src1 dist1 d1]...]# vect source1 -> distance1 distances
INF = float("inf")
ALL = set(range(N))#including sentinel
distances = collections.defaultdict(lambda:INF)
distances[r] = 0

for _ in range(N):
  modified = False
  for src,dst,weight in sdw:
    if distances[dst] > distances[src] + weight:
      distances[dst] = distances[src] + weight
      modified = True
  if modified == False:
    for i in range(N):
      if distances[i] == INF:
        print("INF")
      else:
        print(distances[i])
    exit()
print("NEGATIVE CYCLE")

Submission status: Accepted

Solution code:
# O(EV)
def bellman_ford(s):
    d = [float('inf')]*n # 各頂点への最短距離
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        update = False
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        # 負閉路が存在
        if i == n - 1:
            return -1
    return d

n, w, s = [int(x) for x in input().split()] # n:頂点数, w:辺の数
g = []
for _ in range(w):
    x, y, z = [int(x) for x in input().split()] # 始点,終点,コスト
    g.append([x, y, z])
d = bellman_ford(s)
if d == -1:
    print("NEGATIVE CYCLE")
else:
    for i in d:
        if i == float("inf"):
            print("INF")
        else:
            print(i)

Submission status: Accepted

Solution code:
# 入力１
Vn, En, r = map(int, input().split())

# 入力２：各頂点から別の頂点へ移動する辺とコスト
E = []
for _ in range(En):
    s, t, c = map(int, input().split())
    E.append((s,t,c))

# 初期化
INF = 10**3 * 10**4  # INF 以外で取りうる値は -10**3 * 10**4 < < 10**3 * 10**4
dp = [INF * 10] * Vn
dp[r] = 0

# ベルマン・フォード

# 頂点と同じ回数だけ dp を更新して「伝播」させる
for i in range(Vn):
    for u, v, duv in E:
        if dp[v] > dp[u] + duv:
            dp[v] = dp[u] + duv

# 負のループをチェックする
for u, v, c in E:
    # たどり着けない頂点に関しては無視
    if dp[v] > INF:
        continue
    if dp[u] + c < dp[v]:
        print("NEGATIVE CYCLE")
        break
else:
    # 解答
    for i in range(Vn):
        if not dp[i] > 10**3 * 10**4:  # 頂点数、辺のコストから、この値を下回ることは無いはず
            print(dp[i])
        else:
            print("INF")

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=ja
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class BellmanFord:
    """
    shortest_distance(goal): startノードからgoalノードまでの最短距離
    shortest_path(goal): startノードからgoalノードまでの最短経路
    include_negative_cycle(): 負閉路の存在確認
    """
    def __init__(self, V, edges, start):
        """
        V : 頂点数
        edges: (辺の始点,辺の終点,辺のコスト)を要素とする辺のリスト
        start: 始点のノード番号
        """
        self.V = V
        self.edges = edges
        self.start = start

    def include_negative_cycle(self):
        """
        負閉路の存在確認
        Returns: True or False
        """
        d = [0] * self.V
        for i in range(self.V):
            # start, end, cost
            for s, e, c in self.edges:
                if d[e] > d[s] + c:
                    d[e] = d[s] + c
                    # V回目にも更新があるなら負の閉路が存在する
                    if i == self.V-1:
                        return True
        return False
                    
    def shortest_distance(self):
        """ 
        始点から頂点goalまでの最短距離をを返す 
        """
        d = [float('inf')] * self.V
        d[self.start] = 0

        # 最短経路での1つ前のノードを保持するリスト
        self.prev = [None] * self.V

        loop_counter = 0
        while True:
            update = False
            # start, end, cost
            for s, e, c  in self.edges:
                if d[s] != float('inf') and d[e] > d[s] + c:
                    d[e] = d[s] + c
                    self.prev[e] = s
                    update = True
            
            loop_counter += 1
            if loop_counter == self.V and update:
                d[self.start] = float('inf')
                break

            if not update:
                break
        
        return d

    def shortest_path(self, goal):
        """
        始点から頂点goalまでの最短経路をを返す 
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


def main():
    V, _, r, *edge = map(int, read().split())
    
    Edges = []
    for a, b, w in zip(*[iter(edge)]*3):
        Edges.append((a, b, w))

    bf = BellmanFord(V, Edges, r)
        
    dist = bf.shortest_distance()
    if dist[r] == float('inf'):
        print("NEGATIVE CYCLE")
    else:
        for d in dist:
            print(d if d < float('inf') else "INF")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m, r = map(int, input().split())
E = [tuple(map(int, input().split())) for j in range(m)]
inf = 10**20
D = [inf for i in range(n)]
D[r] = 0
flag = True
cnt = 0
while flag:
    flag = False
    cnt += 1
    if cnt > n:
        print('NEGATIVE CYCLE')
        exit()
    for s, t, d in E:
        if D[s] != inf and D[t] > D[s]+d:
            D[t] = D[s]+d
            flag = True
for i in range(n):
    if D[i] == inf:
        print('INF')
    else:
        print(D[i])

Submission status: Accepted

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

inf = 10**18
d = [inf for i in range(V)]
d[r] = 0
cnt = 0
while True:
    update = False
    for i in range(E):
        e = es[i]
        if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
            d[e[1]] = d[e[0]] + e[2]
            update = True
    if update == False:
        break
    cnt += 1
    if cnt >= V:
        break

if cnt >= V:
    print('NEGATIVE CYCLE')
else:
    for i in range(V):
        if d[i] == inf:
            print('INF')
        else:
            print(d[i])

Submission status: Accepted

Solution code:
INF=10**30
def Belman_Ford(s,N):
    dist=[INF]*N
    dist[s]=0
    cnt=0
    neg=False
    while True:
        if cnt==N:
            break
        update=False
        for f,t,c in Edge:
            if dist[t]>dist[f]+c:
                if cnt<N-1:
                    if dist[f]!=INF:
                        dist[t]=min(dist[t],dist[f]+c)
                        update=True
                else:
                    neg=True
        if not update:
            break
        cnt+=1
    if neg:
        return -1
    else:
        return dist
        
V,E,r=map(int,input().split())
Edge=[tuple(map(int,input().split())) for i in range(E)]

res=Belman_Ford(r,V)
if type(res) is int:
    print('NEGATIVE CYCLE')
else:
    for i in range(V):
        print(res[i] if res[i]!=INF else 'INF')

Submission status: Accepted

Solution code:
def bellmanford(G, s):
    n = len(G)
    inf = float('inf')
    dist = [inf] * n
    dist[s] = 0
    for i in range(2*n):
        for v in range(n):
            for w, c in G[v]:
                if dist[w] > dist[v] + c:
                    dist[w] = dist[v] + c
                    if i >= n - 1:
                        return -1
    return dist
import sys
input = sys.stdin.readline

def main():
    inf = float("inf")
    V, E, r = map(int, input().split())
    graph = [[] for _ in range(V)]
    for _ in range(E):
        s, t, d = map(int, input().split())
        graph[s].append((t, d))
    dist = bellmanford(graph, r)
    if dist == -1:
        print("NEGATIVE CYCLE")
    else:
        for d in dist:
            if d == inf:
                print("INF")
            else:
                print(d)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
v,e,r = map(int,input().split())
std = [ list(map(int,input().split())) for _ in range(e) ]

def BellmanFord(edges,num_v,source):
    #グラフの初期化
    inf = float("inf")
    dist = [ inf for i in range(num_v)]
    dist[source] = 0
    
    #辺の緩和
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]]>(dist[edge[0]]+edge[2]):
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i==(num_v-1):
                    return False,[]
    return True,dist

flag,distance = BellmanFord(std,v,r)
# print(flag)
if flag:
    for i in range(v):
        if distance[i]!=float("inf"):
            print(distance[i])
        else:
            print("INF")
else:
    print("NEGATIVE CYCLE")

Submission status: Accepted

Solution code:
def main():
    N, M, r = map(int, input().split())
    edge = [list(map(int, input().split())) for _ in range(M)]

    dist = [float('inf')] * N
    dist[r] = 0

    for i in range(N):
        flag = False
        for a, b, c in edge:
            if dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                flag = True
        if flag is False:
            break
        else:
            if i == N - 1:
                print('NEGATIVE CYCLE')
                exit()

    for i in range(N):
        if dist[i] == float('inf'):
            print('INF')
        else:
            print(dist[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

def bellman_ford(s):
  dist = [float('inf')]*v 
  dist[s] = 0 
  
  for u in range(v):
    for s, t, d in std:
      if dist[t] > dist[s] + d:
        dist[t] = dist[s] + d 
        if u == v-1:
          return -1
    
  return dist 

dist = bellman_ford(r)
if dist == -1:
  print('NEGATIVE CYCLE')
else:
  for i in range(v):
    if dist[i] == float('inf'):
      print('INF')
      continue 
    print(dist[i])

Submission status: Accepted

Solution code:
nv, ne, r = [int(i) for i in input().split()]
# from, to, cost
edges = [[int(i) for i in input().split()] for _ in range(ne)]
costs = [float("inf")] * nv
costs[r] = 0

for i in range(nv):
    is_updated = False
    for edge in edges:
        f, t, c = edge
        if costs[f] + c < costs[t]:
            costs[t] = costs[f] + c
            is_updated = True

if is_updated:
    print("NEGATIVE CYCLE")
else:
    for c in costs:
        print(c if c < float("inf") else "INF")

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_B
# 単一始点最短経路（負の重みをもつ辺を含む）

# 初期化、入力の処理
INF = float('inf')
edges = []
V, E, r = map(int, input().split())

for i in range(E):
    s, t, d = map(int, input().split())
    edges.append({"s": s, "t": t, "d": d})

# ベルマンフォード法
ds = [INF for i in range(V)]
ds[r] = 0
i = 0
while True:
    i = i + 1
    update = False
    for j in range(E):
        edge = edges[j]
        if ds[edge["s"]] != INF and ds[edge["t"]] > ds[edge["s"]] + edge["d"]:
            if i == V - 1:
                print("NEGATIVE CYCLE")
                exit()

            ds[edge["t"]] = ds[edge["s"]] + edge["d"]
            update = True
    if not update:
        break

for i in range(V):
    print(ds[i] if ds[i] != INF else "INF")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,r = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        v[a].append((b,c))
    d = [float("inf")]*n
    d[r] = 0
    for i in range(n):
        update = 0
        for x in range(n):
            dx = d[x]
            for y,c in v[x]:
                nd = dx+c
                if nd < d[y]:
                    d[y] = nd
                    update = 1
        if not update:
            break
    else:
        print("NEGATIVE CYCLE")
        return
    for i in d:
        if i == float("inf"):
            print("INF")
        else:
            print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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


def bellman_ford(start: int, graph: list):
    """bellman-ford法: 始点startから各頂点への最短距離を求める(負辺OK)
    計算量: O(|E||V|)
    """
    INF = float("inf")
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    if n == 1:
        return False, [0]
    for _ in range(n - 1):
        update = False
        for v, edges in enumerate(graph):
            for nxt_v, cost in edges:
                if dist[nxt_v] > dist[v] + cost:
                    dist[nxt_v] = dist[v] + cost
                    update = True
        if not update:
            break
    else:
        return True, dist  # 負閉路含む
    return False, dist  # 負閉路含まない

v, e, r = map(int, input().split())
info = [list(map(int, input().split())) for i in range(e)]
INF = 10 ** 18

graph = [[] for i in range(v)]
for a, b, cost in info:
    graph[a].append((b, cost))

is_negative, dist = bellman_ford(r, graph)

if is_negative:
    print("NEGATIVE CYCLE")
else:
    for num in dist:
        if num > 10 ** 12:
            print("INF")
        else:
            print(num)

Submission status: Accepted

Solution code:
import sys
from collections import namedtuple, deque


INF = sys.maxsize
Edge = namedtuple('Edge', 's t d')

V, E, r = map(int, input().split())
edges = []

for _ in range(E):
  s, t, d = map(int, input().split())
  edges.append(Edge(s, t, d))

def solve():
  costs = [INF] * V
  costs[r] = 0
  
  for i in range(V):      
    for edge in edges:
      if costs[edge.s] != INF and costs[edge.t] > costs[edge.s] + edge.d:
        if i == V - 1:
          print('NEGATIVE CYCLE')
          return
          
        costs[edge.t] = costs[edge.s] + edge.d        
      
  for x in costs:
    print(x if x != INF else 'INF')

solve()

Submission status: Accepted

Solution code:
n , e , r = map(int,input().split())
inf = 1145141919810364364
es = []

def bf(st):
    d = [inf] * n
    d[st] = 0
    i = 0
    while True:
        update = False
        i += 1
        if i > n:
            return -1
        
        for p,q,r in es:
            if d[p] != inf and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        if update == False:
            break   
            
    return d

for _ in range(e):
    x , y , z = map(int,input().split())
    es.append([x,y,z])

a = bf(r)
if bf(r) == -1:
    print("NEGATIVE CYCLE")
else:
    for i in range(n):
        if a[i] == inf:
            print("INF")
        else:
            print(a[i])

Submission status: Accepted

Solution code:
N, M, S = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b, l = map(int, input().split())
    G[a].append([b, l])
INF = 10**10


def bellman_ford(G, N, S):

    res = [INF for _ in range(N)]
    res[S] = 0
    for _ in range(N-1):
        for i in range(N):
            if res[i] == INF:
                continue
            for sa, sb in G[i]:
                res[sa] = min(res[sa], res[i]+sb)
    for i in range(N):
        if res[i] == INF:
            continue
        for sa, sb in G[i]:
            if res[sa] > res[i]+sb:
                return False
    return res


res = bellman_ford(G, N, S)
if res == False:
    print("NEGATIVE CYCLE")
else:
    for i in range(N):
        if res[i] == INF:
            print("INF")
        else:
            print(res[i])

Submission status: Accepted

Solution code:
from heapq import heappop,heappush,heapify

class Graph():
    def __init__(self,n,edge,directed=False):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append((e[1],e[2]))
            if not directed:
                self.graph[e[1]].append((e[0],e[2]))
    def bellman_ford(self,s,INF=10**18):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        update = True
        for i in range(self.n):
            update = False
            for node, g in enumerate(self.graph):
                for adj,adjcost in g:
                    if dist[node] != INF and dist[node]+adjcost < dist[adj]:
                        dist[adj] = dist[node]+adjcost
                        update = True
            if not update:
                return dist
        return False

INF = 10**18

import sys
input = sys.stdin.readline

V,E,r = map(int,input().split())
edge = [tuple(map(int,input().split())) for _ in range(E)]

g = Graph(V,edge,True)
D = g.bellman_ford(r,INF)

if D:
    for i in range(V):
        if D[i] == INF: D[i] = 'INF'
    print('\n'.join(map(str,D)))

else:
    print('NEGATIVE CYCLE')

Submission status: Accepted

Solution code:
import heapq

n, m, r = list(map(int, input().split()))
V = [i for i in range(n)]
E = [{} for _ in range(n)]

for _ in range(m):
    ef, et, ed = list(map(int, input().split()))
    E[ef][et] = ed
    # E[et][ef] = ed

INF = int(1e18)
dist = {i: INF for i in range(n)}
pred = {i: None for i in range(n)}
dist[r] = 0

update = True
count = 0
while update:
    update = False
    count += 1

    if count > n:
        print("NEGATIVE CYCLE")
        exit()

    for u in range(n):
        for v in E[u]:
            d = E[u][v]
            if dist[u] == INF or dist[u] + d >= dist[v]:
                continue
            else:
                dist[v] = dist[u] + d
                pred[v] = u
                update = True

# check negative cycle
# for u in range(n):
#     for v in E[u]:
#         if dist[u] + E[u][v] < dist[v]:
#             print("NEGATIVE CYCLE")
#             exit(0)

for v in range(n):
    if dist[v] == INF:
        print("INF")
    else:
        print(dist[v])

Submission status: Accepted

Solution code:
inf = float('inf')
# ベルマンフォード法 計算量(VE)
# [引数]: 隣接リスト, 始点, 終点
class Bellmanford:
    def __init__(self, to:list, start:int, goal:int):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.goal = goal
        self.dist = [inf] * self.N
        self.dist[start] = 0
        self.exists_negative_cycle = False
        self.exists_negative_cycle_stog = False
        self.is_updated = [False] * self.N

    # distを更新
    def update(self) -> None:
        for _ in range(self.N - 1):
            for v, s in enumerate(self.to):
                if not s: continue
                for nv, w in s:
                    if self.dist[nv] > self.dist[v] + w:
                        self.dist[nv] = self.dist[v] + w

    # グラフの負閉路検出
    def detection(self) -> bool:
        for v, s in enumerate(self.to):
            if not s: continue
            for nv, w in s:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    self.exists_negative_cycle = True
        return self.exists_negative_cycle

    # スタートからゴールまでのパスの負閉路検出
    def detection_stog(self) -> bool:
        for _ in range(self.N):
            for v, s in enumerate(self.to):
                if not s: continue
                for nv, w in s:
                    if self.dist[nv] > self.dist[v] + w:
                        self.dist[nv] = self.dist[v] + w
                        self.is_updated[nv] = True
                    if self.is_updated[v] is True:
                        self.is_updated[nv] = True
        self.exists_negative_cycle_stog = self.is_updated[self.goal]
        return self.exists_negative_cycle_stog

N, M, r = map(int,input().split())
to = [[] for _ in range(N)]
for _ in range(M):
    s, t, d = map(int,input().split())
    to[s].append((t, d))

BF = Bellmanford(to, r, -1)
BF.update()

if BF.detection():
    print("NEGATIVE CYCLE")
else:
    for d in BF.dist:
        if d == inf:
            print("INF")
        else:
            print(d)