Given a weighted directed graph with n nodes and m edges. Nodes are labeled from 0 to n-1, the task is to check if it contains a negative weight cycle or not.
Note: edges[i] is defined as u, v and weight.
 
Example 1:
Input: n = 3, edges = {{0,1,-1},{1,2,-2},
{2,0,-3}}
Output: 1
Explanation: The graph contains negative weight
cycle as 0->1->2->0 with weight -1,-2,-3.
Example 2:
Input: n = 3, edges = {{0,1,-1},{1,2,-2},
{2,0,3}}
Output: 0
Explanation: The graph does not contain any
negative weight cycle.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function isNegativeWeightCycle() which takes n and edges as input paramater and returns 1 if graph contains negative weight cycle otherwise returns 0.
 
Expected Time Complexity: O(n*m)
Expected Space Compelxity: O(n)
 
Constraints:
1 <= n <= 100
1 <= m <= n*(n-1), where m is the total number of Edges in the directed graph.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

	def isNegativeWeightCycle(self, n, edges):

		#Code here

Solutions:
class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 0 or len(edges) == 0:
			return 0
		distance = [float('inf')] * n
		distance[edges[0][0]] = 0

		def oneTraversal():
			for edge in edges:
				[start, end, weight] = edge
				distance[end] = min(distance[end], distance[start] + weight)
		for i in range(n - 1):
			oneTraversal()
		nextDistance = [i for i in distance]
		oneTraversal()
		return 0 if distance == nextDistance else 1


import sys

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dist = [sys.maxsize for i in range(n)]
		dist[0] = 0
		for i in range(n):
			for e in edges:
				(v1, v2, wt) = e
				if dist[v2] > dist[v1] + wt:
					dist[v2] = dist[v1] + wt
					if i == n - 1:
						return 1
		return 0


import math

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 1:
			return 0

		def bellmanFord(n, edges, dis):
			for i in range(n - 1):
				for e in edges:
					u = e[0]
					v = e[1]
					w = e[2]
					if dis[u] + w < dis[v]:
						dis[v] = dis[u] + w
			return dis
		dis = [math.inf] * n
		dis[edges[0][0]] = 0
		dis = bellmanFord(n, edges, dis)
		for e in edges:
			u = e[0]
			v = e[1]
			w = e[2]
			if dis[u] + w < dis[v]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		visited = [1 for i in range(n)]
		visited[0] = 0
		for i in range(1, n):
			for j in edges:
				u = j[0]
				v = j[1]
				weight = j[2]
				if visited[u] + weight < visited[v]:
					visited[v] = visited[u] + weight
		count = 0
		for i in edges:
			u = i[0]
			v = i[1]
			weight = i[2]
			if visited[u] + weight < visited[v]:
				visited[v] = visited[u] + weight
				count += 1
		if count == 0:
			return 0
		else:
			return 1


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 0 or n == 1:
			return 0
		distance = [float('inf') for i in range(n)]
		distance[edges[0][0]] = 0
		for i in range(n):
			for j in range(len(edges)):
				u = edges[j][0]
				v = edges[j][1]
				w = edges[j][2]
				if distance[u] != float('inf') and distance[u] + w < distance[v]:
					distance[v] = distance[u] + w
		for j in range(len(edges)):
			u = edges[j][0]
			v = edges[j][1]
			w = edges[j][2]
			if distance[u] != float('inf') and distance[u] + w < distance[v]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 1:
			return 0
		dis = [float('inf') for _ in range(n)]
		dis[edges[0][0]] = 0
		for i in range(n - 1):
			for i in edges:
				if dis[i[1]] > dis[i[0]] + i[2]:
					dis[i[1]] = dis[i[0]] + i[2]
		for i in edges:
			if dis[i[1]] > dis[i[0]] + i[2]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 1:
			return 0
		weights = [float('inf') for _ in range(n)]
		weights[edges[0][0]] = 0
		for i in range(n - 1):
			for (u, v, edge_weight) in edges:
				if weights[v] > edge_weight + weights[u]:
					weights[v] = edge_weight + weights[u]
		for (u, v, edge_weight) in edges:
			if weights[v] > edge_weight + weights[u]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 1:
			return 0

		def Solve(edges, n, src):
			dis = [float('inf') for i in range(n)]
			dis[src] = 0
			for i in range(n - 1):
				for j in edges:
					if dis[j[0]] + j[2] < dis[j[1]]:
						dis[j[1]] = dis[j[0]] + j[2]
			for i in edges:
				if dis[i[1]] > dis[i[0]] + i[2]:
					return 1
			return 0
		return Solve(edges, n, edges[0][0])


class Solution:

	def isNegativeWeightCycle(self, V, edges):
		if n == 1:
			return 0
		d = [100000000 for i in range(V)]
		d[edges[0][0]] = 0
		for j in range(V - 1):
			for i in edges:
				u = i[0]
				v = i[1]
				w = i[2]
				if d[u] != 100000000 and d[u] + w < d[v]:
					d[v] = d[u] + w
		for i in edges:
			u = i[0]
			v = i[1]
			w = i[2]
			if d[u] != 100000000 and d[u] + w < d[v]:
				return 1
		return 0


import sys

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if len(edges) == 0:
			return 0
		d = [float('inf') for i in range(n)]
		d[edges[0][0]] = 0
		for i in range(n - 1):
			for edge in edges:
				if d[edge[0]] + edge[2] < d[edge[1]]:
					d[edge[1]] = d[edge[0]] + edge[2]
		for edge in edges:
			if d[edge[0]] + edge[2] < d[edge[1]]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dist = [0 for i in range(n)]
		for i in range(n):
			relaxed = False
			for e in edges:
				(u, v, w) = (e[0], e[1], e[2])
				if dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
					relaxed = True
		if relaxed == False:
			return 0
		return 1


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		d = [0 for i in range(n)]
		for i in range(n):
			relaxed = False
			for e in edges:
				if d[e[0]] + e[2] < d[e[1]]:
					d[e[1]] = d[e[0]] + e[2]
					relaxed = True
		if relaxed == False:
			return 0
		return 1


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		inf = 1000000000000000000
		d = [0 for i in range(n)]
		for i in range(n):
			x = -1
			for e in edges:
				if d[e[0]] + e[2] < d[e[1]]:
					d[e[1]] = d[e[0]] + e[2]
					x = e[1]
		if x == -1:
			return 0
		return 1


class Solution:

	def isNegativeWeightCycle(self, n, edges):

		def bellmanFord(soure, dist):
			for i in range(1, n + 1):
				for edge in edges:
					(u, v, w) = (edge[0], edge[1], edge[2])
					dist[v] = min(dist[v], dist[u] + w)
			for edge in edges:
				(u, v, w) = (edge[0], edge[1], edge[2])
				if dist[u] + w < dist[v]:
					return 1
			return 0
		for i in range(n):
			source = i
			dist = [float('inf') for i in range(n)]
			dist[source] = 0
			if bellmanFord(source, dist) == 1:
				return 1
		return 0


def is_negative_cycle_present(v: int, edges: [[]]):
	if len(edges) == 0:
		return False
	distance_arr = [float('inf') for i in range(v)]
	distance_arr[edges[0][0]] = 0
	for i in range(v - 1):
		for edge in edges:
			start = edge[0]
			end = edge[1]
			weight = edge[2]
			if distance_arr[start] != float('inf') and distance_arr[end] > distance_arr[start] + weight:
				distance_arr[end] = distance_arr[start] + weight
	for edge in edges:
		start = edge[0]
		end = edge[1]
		weight = edge[2]
		if distance_arr[end] > distance_arr[start] + weight:
			return True
	return False

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		return 1 if is_negative_cycle_present(n, edges) else 0


import math

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 1:
			return 0
		distances = {i: math.inf for i in range(n)}
		distances[edges[0][0]] = 0
		for _ in range(n - 1):
			for (u, v, w) in edges:
				if distances[u] != math.inf and distances[v] > distances[u] + w:
					distances[v] = distances[u] + w
		for (u, v, w) in edges:
			if distances[u] != math.inf and distances[v] > distances[u] + w:
				return 1
		return 0


import sys

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if len(edges) == 0:
			return 0
		dist = [float('inf')] * n
		dist[edges[0][0]] = 0

		def relax(u, v, wt):
			if dist[u] + wt < dist[v]:
				dist[v] = dist[u] + wt
		for it in range(n - 1):
			for (u, v, wt) in edges:
				relax(u, v, wt)
		for (u, v, wt) in edges:
			if dist[u] + wt < dist[v]:
				return 1
		return 0


import sys

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dist = [sys.maxsize] * n
		dist[0] = 0
		for count in range(n - 1):
			for edge in edges:
				if dist[edge[0]] + edge[2] < dist[edge[1]]:
					dist[edge[1]] = dist[edge[0]] + edge[2]
		new_dist = dist.copy()
		for edge in edges:
			if dist[edge[0]] + edge[2] < dist[edge[1]]:
				dist[edge[1]] = dist[edge[0]] + edge[2]
		for i in range(n):
			if dist[i] != new_dist[i]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if len(edges) == 0:
			return 0
		dist = [float('inf')] * n
		start = edges[0][0]
		dist[start] = 0
		for i in range(n - 1):
			for (u, v, d) in edges:
				if dist[v] > dist[u] + d:
					dist[v] = dist[u] + d
		for (u, v, d) in edges:
			if dist[v] > dist[u] + d:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 1:
			return 0
		dist = [float('inf') for i in range(n)]
		dist[edges[0][0]] = 0
		for i in range(n):
			for j in edges:
				(u, v, w) = j
				if dist[u] + w < dist[v]:
					if i == n - 1:
						return 1
					dist[v] = dist[u] + w
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dist = [100000 for i in range(n)]
		dist[0] = 0
		for i in range(n):
			for j in range(len(edges)):
				(src, dest, weight) = (edges[j][0], edges[j][1], edges[j][2])
				if dist[src] + weight < dist[dest]:
					dist[dest] = dist[src] + weight
		for i in range(n):
			for j in range(len(edges)):
				(src, dest, weight) = (edges[j][0], edges[j][1], edges[j][2])
				if dist[src] + weight < dist[dest]:
					return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 1:
			return 0
		dist = [float('inf')] * n
		dist[edges[0][0]] = 0
		for i in range(n - 1):
			for it in edges:
				u = it[0]
				v = it[1]
				wt = it[2]
				if dist[u] + wt < dist[v]:
					dist[v] = dist[u] + wt
		c = 0
		for it in edges:
			u = it[0]
			v = it[1]
			wt = it[2]
			if dist[u] + wt < dist[v]:
				c = 1
		if c == 1:
			return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		distance = [-1] * n
		distance[0] = 0
		for i in range(n):
			for edge in edges:
				d = distance[edge[0]] + edge[2]
				if distance[edge[1]] == -1 or distance[edge[1]] > d:
					distance[edge[1]] = d
		for edge in edges:
			d = distance[edge[0]] + edge[2]
			if distance[edge[1]] > d:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dist = [1000000000.0] * n
		m = len(edges)
		dist[0] = 0
		for _ in range(n - 1):
			for i in range(m):
				if edges[i][2] + dist[edges[i][0]] < dist[edges[i][1]]:
					dist[edges[i][1]] = edges[i][2] + dist[edges[i][0]]
		for i in range(m):
			if edges[i][2] + dist[edges[i][0]] < dist[edges[i][1]]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 1:
			return 0
		dest = [float('inf')] * n
		dest[edges[0][0]] = edges[0][2]
		for i in range(n):
			for j in edges:
				(u, v, weight) = (j[0], j[1], j[2])
				if dest[u] != float('inf') and dest[u] + weight < dest[v]:
					dest[v] = dest[u] + weight
		flag = 0
		for j in edges:
			(u, v, weight) = (j[0], j[1], j[2])
			if dest[u] != float('inf') and dest[u] + weight < dest[v]:
				dest[v] = dest[u] + weight
				flag = 1
		if flag == 1:
			return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		isneg = 0
		dist = [float('Inf')] * n
		if len(edges) == 0:
			return 0
		dist[edges[0][0]] = 0
		for _ in range(n - 1):
			for (u, v, w) in edges:
				if dist[u] != float('Inf') and dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
		for (u, v, w) in edges:
			if dist[u] != float('Inf') and dist[u] + w < dist[v]:
				dist[v] = dist[u] + w
				isneg = 1
		return isneg


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 1:
			return 0
		distance = [10 ** 18 for i in range(n)]
		distance[edges[0][0]] = 0
		for i in range(1, n):
			for j in range(len(edges)):
				u = edges[j][0]
				v = edges[j][1]
				wt = edges[j][2]
				if distance[u] != 10 ** 18 and distance[u] + wt < distance[v]:
					distance[v] = distance[u] + wt
		for j in range(len(edges)):
			u = edges[j][0]
			v = edges[j][1]
			wt = edges[j][2]
			if distance[u] != 10 ** 18 and distance[u] + wt < distance[v]:
				return 1
		return 0


import sys

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if len(edges) == 0:
			return 0
		INF = sys.maxsize
		dist = [INF] * n
		dist[edges[0][0]] = 0
		for i in range(n - 1):
			for (u, v, wt) in edges:
				if dist[u] != INF and dist[u] + wt < dist[v]:
					dist[v] = dist[u] + wt
		for (u, v, wt) in edges:
			if dist[u] != INF and dist[u] + wt < dist[v]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		adj_list = {}
		for i in range(n):
			adj_list[i] = []
		for (i, j, k) in edges:
			adj_list[i].append((j, k))
		distance = {}
		for i in adj_list.keys():
			distance[i] = float('inf')
		for i in adj_list.keys():
			if adj_list[i] != []:
				distance[i] = 0
				break
		for i in range(len(adj_list.keys()) - 1):
			for j in adj_list.keys():
				for (n, w) in adj_list[j]:
					if distance[n] > distance[j] + w:
						distance[n] = distance[j] + w
		for i in adj_list.keys():
			for (n, w) in adj_list[i]:
				if distance[n] > distance[i] + w:
					return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dp = [float('inf') for i in range(n)]
		if n == 1:
			return 0
		dp[edges[0][0]] = 0
		for i in range(n - 1):
			for edge in edges:
				if dp[edge[1]] > dp[edge[0]] + edge[2]:
					dp[edge[1]] = dp[edge[0]] + edge[2]
		for edge in edges:
			if dp[edge[1]] > dp[edge[0]] + edge[2]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dist = [float('inf')] * n
		dist[0] = 0
		for i in range(n - 1):
			for j in range(len(edges)):
				src = edges[j][0]
				dest = edges[j][1]
				wigh = edges[j][2]
				if dist[src] != float('inf') and dist[src] + wigh < dist[dest]:
					dist[dest] = wigh + dist[src]
		for j in range(0, len(edges)):
			src = edges[j][0]
			dest = edges[j][1]
			wigh = edges[j][2]
			if dist[src] != float('inf') and dist[src] + wigh < dist[dest]:
				return 1
		return 0

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 1:
			return 0
		dis = [float('inf') for _ in range(n)]
		dis[edges[0][0]] = 0
		for i in range(n - 1):
			for i in edges:
				if dis[i[1]] > dis[i[0]] + i[2]:
					dis[i[1]] = dis[i[0]] + i[2]
		for i in edges:
			if dis[i[1]] > dis[i[0]] + i[2]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dist = [float('inf')] * n
		if edges:
			dist[edges[0][0]] = 0
		else:
			return 0
		for _ in range(n - 1):
			for (u, v, w) in edges:
				if dist[u] != float('inf') and dist[v] > dist[u] + w:
					dist[v] = dist[u] + w
		for (u, v, w) in edges:
			if dist[u] != float('inf') and dist[v] > dist[u] + w:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 1:
			return 0
		d = [float('inf')] * n
		s = edges[0][0]
		d[s] = 0
		for _ in range(n - 1):
			for (u, v, w) in edges:
				if d[v] > d[u] + w:
					d[v] = d[u] + w
		nc = False
		for (u, v, w) in edges:
			if d[v] > d[u] + w:
				nc = True
				d[v] = d[u] + w
				break
		return 1 if nc else 0


class Solution:

	def isNegativeWeightCycle(self, V, edges):
		distance = [0 for i in range(V)]
		for visit in range(V - 1):
			for (u, v, wt) in edges:
				if distance[v] == 0 or distance[u] + wt < distance[v]:
					distance[v] = distance[u] + wt
		for (u, v, wt) in edges:
			if distance[u] != int(100000000.0) and distance[u] + wt < distance[v]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		from math import inf
		dist = [inf] * (n + 1)

		def bellman(start, n, edges):
			dist[start] = 0
			for i in range(n):
				for ed in edges:
					(cnt, nxt, w) = (ed[0], ed[1], ed[2])
					if dist[nxt] > dist[cnt] + w:
						dist[nxt] = dist[cnt] + w
						if i == n - 1:
							return 1
			return 0
		for i in range(n):
			if dist[i] == inf:
				b = bellman(i, n, edges)
				if b == 1:
					return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		res = [1000000] * n
		res[0] = 0
		for i in range(n - 1):
			for edge in edges:
				vert1 = edge[0]
				vert2 = edge[1]
				edgeWeight = edge[2]
				if res[vert2] > edgeWeight + res[vert1]:
					res[vert2] = edgeWeight + res[vert1]
		testRes = res.copy()
		for edge in edges:
			vert1 = edge[0]
			vert2 = edge[1]
			edgeWeight = edge[2]
			if testRes[vert2] > edgeWeight + testRes[vert1]:
				testRes[vert2] = edgeWeight + testRes[vert1]
		if testRes == res:
			return 0
		else:
			return 1


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if not edges:
			return 0
		d = [float('inf')] * n
		d[edges[0][0]] = 0
		for i in range(n - 1):
			for (u, v, w) in edges:
				if d[v] > d[u] + w:
					d[v] = d[u] + w
		for (u, v, w) in edges:
			if d[v] > d[u] + w:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 0 or n == 1:
			return 0
		dist = [float('inf') for i in range(n)]
		src = edges[0][0]
		dist[src] = 0
		for i in range(n):
			for edge in edges:
				u = edge[0]
				v = edge[1]
				wt = edge[2]
				if dist[u] != float('inf') and dist[u] + wt < dist[v]:
					dist[v] = dist[u] + wt
		for edge in edges:
			u = edge[0]
			v = edge[1]
			wt = edge[2]
			if dist[u] != float('inf') and dist[u] + wt < dist[v]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if n == 1:
			return 0
		dist = [100000 for i in range(n)]
		dist[edges[0][0]] = 0
		for i in range(1, n):
			for j in range(len(edges)):
				u = edges[j][0]
				v = edges[j][1]
				w = edges[j][2]
				if dist[u] != 100000 and dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
		for i in range(len(edges)):
			u = edges[i][0]
			v = edges[i][1]
			w = edges[i][2]
			if dist[u] != 100000 and dist[u] + w < dist[v]:
				return 1
		return 0


INF = 100000000

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dist = [INF] * n
		dist[0] = 0
		for i in range(n - 1):
			for (u, v, wt) in edges:
				if dist[u] != 100000000 and dist[u] + wt < dist[v]:
					dist[v] = dist[u] + wt
		for (u, v, wt) in edges:
			if dist[u] + wt < dist[v]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dist = [float('inf')] * n

		def bellman(src):
			dist[src] = 0
			for _ in range(1, n):
				for (u, v, edgeWt) in edges:
					if dist[v] > dist[u] + edgeWt:
						dist[v] = dist[u] + edgeWt
			for (u, v, edgeWt) in edges:
				if dist[v] > dist[u] + edgeWt:
					return 1
			return 0
		for i in range(n):
			if dist[i] == float('inf'):
				if bellman(i):
					return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dist = [100000] * n
		dist[0] = 0
		for i in range(1, n):
			for edge in edges:
				u = edge[0]
				v = edge[1]
				weight = edge[2]
				if dist[u] + weight < dist[v]:
					dist[v] = dist[u] + weight
		change = 0
		for edge in edges:
			u = edge[0]
			v = edge[1]
			weight = edge[2]
			if dist[u] + weight < dist[v]:
				dist[v] = dist[u] + weight
				change += 1
		return 0 if change == 0 else 1


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dist = [10 ** 6] * n
		if n == 1:
			return 0
		dist[edges[0][0]] = 0
		for i in range(n):
			for j in edges:
				if dist[j[0]] == 10 ** 6:
					dist[j[0]] = 0
				if dist[j[0]] + j[2] < dist[j[1]] and i == n - 1:
					return 1
				dist[j[1]] = min(dist[j[1]], dist[j[0]] + j[2])
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		d = [100000] * n
		d[0] = 0
		for i in range(1, n):
			for e in edges:
				u = e[0]
				v = e[1]
				w = e[2]
				if d[u] + w < d[v]:
					d[v] = d[u] + w
		c = 0
		for e in edges:
			u = e[0]
			v = e[1]
			w = e[2]
			if d[u] + w < d[v]:
				d[v] = d[u] + w
				c += 1
		return 0 if c == 0 else 1


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		d = [float('inf')] * n
		d[0] = 0
		for _ in range(n - 1):
			for edge in edges:
				(u, v, w) = edge
				d[v] = min(d[v], d[u] + w)
		for edge in edges:
			(u, v, w) = edge
			if d[v] > d[u] + w:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if not edges:
			return 0
		dist = [2147483647] * n
		dist[edges[0][0]] = 0
		for i in range(n + 5):
			for (u, v, w) in edges:
				if dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
		for (u, v, w) in edges:
			if dist[u] + w < dist[v]:
				return 1
		return 0


import array

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if not edges:
			return 0
		dist = array.array('i', [2147483647] * n)
		dist[edges[0][0]] = 0
		updated = False
		for i in range(n - 1):
			updated = False
			for (u, v, w) in edges:
				if dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
					updated = True
			if not updated:
				return 0
		for (u, v, w) in edges:
			if dist[u] + w < dist[v]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		distance = [float('inf')] * n
		distance[0] = 0
		for i in range(n):
			for (u, v, w) in edges:
				if distance[u] != float('inf') and distance[u] + w < distance[v]:
					distance[v] = distance[u] + w
		for (u, v, w) in edges:
			if distance[u] != float('inf') and distance[u] + w < distance[v]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		dist = [float('Inf')] * n
		dist[0] = 0
		for _ in range(n - 1):
			for (s, d, w) in edges:
				if dist[s] != float('Inf') and dist[s] + w < dist[d]:
					dist[d] = dist[s] + w
		for (s, d, w) in edges:
			if dist[s] != float('Inf') and dist[s] + w < dist[d]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n: int, edges) -> int:
		distances = {i: float('inf') for i in range(1, n + 1)}
		distances[0] = 0
		for _ in range(n - 1):
			updated = False
			for (u, v, w) in edges:
				if distances[u] + w < distances[v]:
					distances[v] = distances[u] + w
					updated = True
			if not updated:
				break
		for (u, v, w) in edges:
			if distances[u] + w < distances[v]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n: int, edges) -> int:
		tab = [0] + [5000] * len(edges)
		for i in range(n):
			updated = False
			for edge in edges:
				if tab[edge[0]] + edge[2] < tab[edge[1]]:
					tab[edge[1]] = tab[edge[0]] + edge[2]
					updated = True
			if not updated:
				return 0
		return 1


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if not edges:
			return 0
		dist = [10000] * n
		dist[edges[0][0]] = 0
		for _ in range(n - 1):
			for (u, v, w) in edges:
				if dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
		for (u, v, w) in edges:
			if dist[u] + w < dist[v]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		nodes = [0]
		for i in range(n - 1):
			nodes.append(0)
		for i in range(n - 1):
			for edge in edges:
				if nodes[edge[1]] > nodes[edge[0]] + edge[2]:
					nodes[edge[1]] = nodes[edge[0]] + edge[2]
		for edge in edges:
			if nodes[edge[1]] > nodes[edge[0]] + edge[2]:
				return 1
		return 0


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		visited = [False] * n
		recent = [False] * n
		adjestend_list = [[] for _ in range(n)]
		for i in edges:
			adjestend_list[i[0]].append([i[1], i[2]])

		def dfs(curr, adjestend_list, w):
			visited[curr] = 1
			recent[curr] = 1
			for i in adjestend_list[curr]:
				if visited[i[0]] == 0:
					if dfs(i[0], adjestend_list, w + i[1]) == 1:
						return 1
				elif recent[i[0]] == True and w + i[1] < 0:
					return 1
			recent[curr] = 0
			visited[curr] = 0
			return False
		for i in range(n):
			if visited[i] == 0:
				if dfs(i, adjestend_list, 0) == 1:
					return 1
		return 0


import array

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if not edges:
			return 0
		dist = array.array('i', [2147483647] * n)
		dist[edges[0][0]] = 0
		for (u, v, w) in edges:
			if dist[u] + w < dist[v]:
				dist[v] = dist[u] + w
		for (u, v, w) in edges:
			if dist[u] + w < dist[v]:
				return 1
		return 0


import array

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if not edges:
			return 0
		dist = array.array('i', [2147483647] * n)
		dist[edges[0][0]] = 0
		for _ in range(n - 1):
			for (u, v, w) in edges:
				new_dist = dist[u] + w
				cur_dist = dist[v]
				if new_dist < cur_dist:
					dist[v] = new_dist
		for (u, v, w) in edges:
			if dist[u] + w < dist[v]:
				return 1
		return 0


import numpy as np
import array

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if not edges:
			return 0
		dist = array.array('q', [4294967295] * n)
		dist[edges[0][0]] = 0
		for _ in range(n - 1):
			for (u, v, w) in edges:
				new_dist = dist[u] + w
				cur_dist = dist[v]
				if new_dist < cur_dist:
					dist[v] = new_dist
		for (u, v, w) in edges:
			if dist[u] + w < dist[v]:
				return 1
		return 0


import numpy

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if not edges:
			return 0
		dist = [4294967295] * n
		dist[edges[0][0]] = 0
		for _ in range(n - 1):
			for (u, v, w) in edges:
				if dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
		for (u, v, w) in edges:
			if dist[u] + w < dist[v]:
				return 1
		return 0


import numpy

class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if not edges:
			return 0
		dist = [4294967295] * n
		dist[edges[0][0]] = 0
		for i in range(n + 1):
			updated = False
			for (u, v, w) in edges:
				if dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
					updated = True
			if not updated:
				return 0
			elif i == n:
				return 1


class Solution:

	def isNegativeWeightCycle(self, n, edges):
		if not edges:
			return 0
		dist = [4294967295] * n
		dist[edges[0][0]] = 0
		for _ in range(n - 1):
			updated = False
			for (u, v, w) in edges:
				if dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
					updated = True
			if not updated:
				return 0
		for (u, v, w) in edges:
			if dist[u] + w < dist[v]:
				return 1
		return 0