Problem:
 Score : 400 points    Problem Statement There are N people standing on the x -axis.
Let the coordinate of Person i be x_i .
For every i , x_i is an integer between 0 and 10^9 (inclusive).
It is possible that more than one person is standing at the same coordinate.  You will given M pieces of information regarding the positions of these people.
The i -th piece of information has the form (L_i, R_i, D_i) .
This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_{R_i} - x_{L_i} = D_i holds.  It turns out that some of these M pieces of information may be incorrect.
Determine if there exists a set of values (x_1, x_2, ..., x_N) that is consistent with the given pieces of information.      Constraints  1 \leq N \leq 100  000  0 \leq M \leq 200  000  1 \leq L_i, R_i \leq N ( 1 \leq i \leq M )  0 \leq D_i \leq 10  000 ( 1 \leq i \leq M )  L_i \neq R_i ( 1 \leq i \leq M )  If i \neq j , then (L_i, R_i) \neq (L_j, R_j) and (L_i, R_i) \neq (R_j, L_j) .  D_i are integers.         Input Input is given from Standard Input in the following format:  N  M  L_1  R_1  D_1  L_2  R_2  D_2  :  L_M  R_M  D_M       Output If there exists a set of values (x_1, x_2, ..., x_N) that is consistent with all given pieces of information, print Yes ; if it does not exist, print No .        Sample Input 1 3 3
1 2 1
2 3 1
1 3 2      Sample Output 1 Yes  Some possible sets of values (x_1, x_2, x_3) are (0, 1, 2) and (101, 102, 103) .       Sample Input 2 3 3
1 2 1
2 3 1
1 3 5      Sample Output 2 No  If the first two pieces of information are correct, x_3 - x_1 = 2 holds, which is contradictory to the last piece of information.       Sample Input 3 4 3
2 1 1
2 3 5
3 4 2      Sample Output 3 Yes       Sample Input 4 10 3
8 7 100
7 9 100
9 8 100      Sample Output 4 No       Sample Input 5 100 0      Sample Output 5 Yes

Solution (Python):
def ans():
    NOT_VISITED = -99999
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    visited = [NOT_VISITED for _ in range(N + 1)]

    def dps(graph, start, visited):
        if visited[start] != NOT_VISITED:
            return False
        stuck = [start]
        visited[start] = 0
        while stuck:
            label = stuck.pop()
            for nextnode, distance in graph[label]:
                if visited[nextnode] == NOT_VISITED:
                    stuck.append(nextnode)
                    visited[nextnode] = visited[label] + distance
                elif visited[nextnode] != visited[label] + distance:
                    return True

    for _ in range(M):
        L, R, D = map(int, input().split())
        graph[L].append((R, D))
        graph[R].append((L, -D))

    for i in range(1, N + 1):
        if dps(graph, i, visited):
            return print('No')
    return print('Yes')

ans()

Solution (Python):
import sys
sys.setrecursionlimit(2000002)

def DFS(i, pos, connected, distances):
  if pos[i] == None:
    pos[i] = 0
  size = len(connected[i])
  for j in range(size):
    if pos[connected[i][j]] == None:
      pos[connected[i][j]] = pos[i] + distances[i][j]
      if DFS(connected[i][j], pos, connected, distances) == False:
        return False
    elif pos[connected[i][j]] != pos[i] + distances[i][j]:
      return False
  return True

N, M = map(int, input().split())
pos = [None for i in range(N + 1)]
connected = [[] for i in range(N + 1)]
distances = [[] for i in range(N + 1)]
for i in range(M):
  l, r, d = map(int, input().split())
  connected[l].append(r)
  distances[l].append(d)
  connected[r].append(l)
  distances[r].append(-d)
judge = True
for i in range(1, N + 1):
  if pos[i] == None:
    judge = DFS(i, pos, connected, distances)
    if judge == False:
      break
if judge:
  print('Yes')
else:
  print('No')

Solution (Python):
import sys
sys.setrecursionlimit(200002)

N,M=map(int,input().split())
mp=[[] for i in range(N+1)]
for i in range(M):
  L,R,D=map(int,input().split())
  mp[L].append([R,D])
  mp[R].append([L,-D])

dist=[None]*(N+1)

def dfs(n):
  for np,nd in mp[n]:
    if dist[np] is None:
      dist[np]=dist[n]+nd
      if not dfs(np):
        return False
    else:
      if dist[np]!=dist[n]+nd:
        return False
  return True
ans=True
for i in range(1,N+1):
  if dist[i] is None:
    dist[i]=0
    if not dfs(i):
      ans=False
      break
if ans:
  print("Yes")
else:
  print("No")

Solution (Python):

"""
https://beta.atcoder.jp/contests/abc087/tasks/arc090_b

"""
import sys
from sys import stdin
from heapq import heappush, heappop
input = stdin.readline




def solve(data, N):
    scores = [-1] * (N+1)
    graphs = [[] for _ in range(N+1)]
    in_degs = [0] * (N+1)

    for l, r, d in data:
        in_degs[r] += 1
        graphs[l].append((r, d))

    pq = []

    for pos in range(1, N+1):
        if in_degs[pos] == 0:
            heappush(pq, pos)

    cs = 1
    while pq:
        pos = heappop(pq)
        if scores[pos] < 0:
            scores[pos] = cs
        for r, d in graphs[pos]:
            if scores[r] < 0:
                scores[r] = scores[pos] + d
            else:
                if scores[r] != scores[pos] + d:
                    return 'No'
            in_degs[r] -= 1
            if in_degs[r] == 0:
                heappush(pq, r)

    for d in in_degs[1:]:
        if d > 0:
            return 'No'
    return 'Yes'


def main(args):
    N, M = map(int, input().split())
    data = []
    for _ in range(M):
        l, r, d = map(int, input().split())
        data.append((l, r, d))
    ans = solve(data, N)
    print(ans)


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

Solution (Python):
from collections import deque
from collections import defaultdict

N,M=map(int,raw_input().split())
nl=[ [] for i in range(N+1) ]
cost={}

for i in range(M):
	L,R,D=map(int,raw_input().split())
	if i==0:start=L
	nl[L].append(R)
	nl[R].append(L)
	cost[(L,R)]=D
	cost[(R,L)]=-D


d=[ None for i in range(N+1) ]
V=[ 0 for i in range(N+1) ]

def dfs(start):
	q = deque([]) 
	V[start]=1
	d[start]=0
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i]!=1:
				V[i]=1
				q.append(i)
				d[i]=d[v]+cost[(v,i)]
			else:
				if d[i]-d[v]!=cost[(v,i)]:
					print "No"
					quit()

for i in range(1,N+1):
	if V[i]==0:
		dfs(i)
else:
	print "Yes"

Solution (Python):
import sys
sys.setrecursionlimit(200002)


def dfs(i, c):
    C[i] = True
    P[i] = c
    for t in G[i]:
        if (C[t[0]] == True):
            continue
        dfs(t[0], c+t[1])
    return


N, M = list(map(int, input().split()))
G = [[] for _ in range(N+1)]
P = [None for _ in range(N+1)]
C = [False for _ in range(N+1)]

for i in range(M):
    l, r, d = list(map(int, input().split()))
    G[l].append((r,d))
    G[r].append((l,-d))

for i in range(1, N+1):
    if (C[i] == False):
        dfs(i,0)

f = False
for i in range(1, N+1):
    for t in G[i]:
        if ((P[t[0]] - P[i]) != t[1]):
            f = True
if (f):
    print('No')
else:
    print('Yes')

Solution (Python):
import sys
sys.setrecursionlimit(200002)

def dfs(s):
	global x, G
	for t, d in G[s]:
		if x[t] is None:
			x[t] = x[s] + d
			if not dfs(t):
				return False
		else:
			if x[t] != x[s] + d:
				return False
	return True

N,M = map(int,input().split())
x = [None] * N
G = [[] for _ in range(N)]
for _ in range(M):
	L, R, D = map(int,input().split())
	G[L-1].append([R-1,D])
	G[R-1].append([L-1,-D])

res = True
for i in range(N):
	if x[i] is None:
		x[i] = 0
		res &= dfs(i)

print("Yes" if res == True else "No")

Solution (Python):
NOT_VISIT = 10**20
N, M = map(int,input().split())
graph = [[] for i in range(N)]

for i in range(M):
	L, R, D = map(int,input().split())
	graph[L-1].append((R-1,D))
	graph[R-1].append((L-1,-D))

visited = [NOT_VISIT for i in range(N)]

def dfs(start):
	global graph, visited

	if visited[start] != NOT_VISIT:
		return True

	stack = [start]
	visited[start] = 0
	while stack:
		label = stack.pop()
		for nextnode, distance in graph[label]:
			if visited[nextnode] == NOT_VISIT:
				stack.append(nextnode)
				visited[nextnode] = visited[label] + distance
			elif visited[nextnode] != visited[label] + distance:
				return False
	return True

res = True
for i in range(N):
	res &= dfs(i)

print("Yes" if res == True else "No")

Solution (Python):


def dfs(graph, start, visited):
    if visited[start] != -99999:
        return True
    
    stack = [start]
    visited[start] = 0
    while stack:
        label = stack.pop()
        for nextnode, distance in graph[label]:
            if visited[nextnode] == -99999:
                stack.append(nextnode)
                visited[nextnode] = visited[label] + distance
            elif visited[nextnode] != visited[label] + distance:
                return False
    return True

N, M = (int(i) for i in input().split())  

graph = [[] for i in range(N+1)]

for i in range(M):
    L, R, D = (int(i) for i in input().split())
    graph[L].append((R, D))
    graph[R].append((L, -1 * D))


visited = [-99999 for i in range(N+1)]

flag = True
for i in range(1, N + 1):
    ans = dfs(graph, i, visited)
    if not ans:
        flag = False
        break

if flag:
    print('Yes')
else:
    print('No')

Solution (Python):
def d_People_on_a_Line(N, M, P):
    if M == 0:
        return 'Yes'

    adj = [[] for _ in range(N)]  
    for l, r, d in P:
        adj[l - 1].append([r - 1, d])
        adj[r - 1].append([l - 1, -d])

    dist = [None for _ in range(N)]
    for i in range(N):  
        if dist[i] is not None:
            
            continue
        stack = [i]
        dist[i] = 0  
        while stack:
            v = stack.pop()  
            for to, cost in adj[v]:
                if dist[to] is None:
                    
                    stack.append(to)
                    dist[to] = dist[v] + cost
                elif dist[to] != dist[v] + cost:
                    
                    
                    return 'No'
    return 'Yes'  

N,M = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(M)]
print(d_People_on_a_Line(N, M, P))

Solution (Python):

import sys
sys.setrecursionlimit(200002)

def dfs(s):
    for t, d in G[s]:
        if x[t] is None:
            x[t] = x[s] + d
            if not dfs(t):
                return False
        else:
            if x[t] - x[s] != d:
                return False
    return True

N, M = map(int, input().split())
x = [None] * N
G = [[] for _ in range(N)]
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L].append([R, D])
    G[R].append([L, -D])
ans = True
for i in range(N):
    if x[i] is None:
        x[i] = 0
        if not dfs(i):
            ans = False
print(('No', 'Yes')[ans])

Solution (Python):
class UnionFindTree:
    def __init__(self, size):
        self.parent = list(range(size))
        self.dist = [0] * size

    def find_root(self, x):
        if self.parent[x] == x:
            return x, 0
        else:
            self.parent[x], d = self.find_root(self.parent[x])
            self.dist[x] += d
            return self.parent[x], self.dist[x]

    def union(self, x, y, d):
        r1, d1 = self.find_root(x)
        r2, d2 = self.find_root(y)
        if r1 != r2:
            self.parent[r2] = r1
            self.dist[r2] = (d1 - d2) + d
        else:
            if (d2 - d1) != d:
                return False
        return True

def main():
    n, m = map(int, input().split())
    tree = UnionFindTree(n+1)
    for i in range(m):
        l, r, d = map(int, input().split())
        if not tree.union(l, r, d):
            print('No')
            return
    print('Yes')

main()

Solution (Python):
import collections
from pprint import pprint as pp

N,M = tuple(map(int, input().split()))
LRD = collections.defaultdict(list)
Lset = set()
Rset = set()
for _ in range(M):
  l,r,d = map(int, input().split())
  l -= 1
  r -= 1
  LRD[l].append((r,d))
  Lset.add(l)
  Rset.add(r)

n = [ None for _ in range(N) ]

deq = collections.deque()

def func(l):
  lst = LRD.pop(l,[])
  for r,d in lst:
    if n[l] != None:
      d2 = n[l] + d
    else:
      n[l] = 0
      d2 = d
    if n[r] not in (d2, None):
      return True
    n[r] = d2
    deq.append(r)
  return False

def func2():
  lst = Lset-Rset
  for l in lst:
    n[l] = 0
    deq.append(l)
  while deq:
    l = deq.popleft()
    if l in LRD:
      if func(l):
        return True
  deq.extend(LRD.keys())
  while deq:
    l = deq.popleft()
    if l in LRD:
      if func(l):
        return True
  return False

if func2():
  print('No')
else:
  print('Yes')

Solution (Python):
from collections import deque

N, M = map(int, input().split())
edges = {}
connections = {}
for _ in range(M):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    assert (l, r) not in edges
    assert (r, l) not in edges
    edges[l, r] = d

    if l not in connections:
        connections[l] = set()
    if r not in connections:
        connections[r] = set()
    connections[l].add(r)
    connections[r].add(l)


def solve():
    fixed = [None] * N
    undone = set(range(N))

    while undone:
        start = undone.pop()
        undone.add(start)
        queue = deque()
        queue.append(start)

        while queue:
            x = queue.popleft()
            if x not in undone:
                continue
            undone.remove(x)
            if x not in connections:
                continue

            for y in connections[x]:
                if y in undone:
                    queue.append(y)
                if (x, y) in edges:
                    if fixed[x] is None:
                        if fixed[y] is None:
                            fixed[x] = 0
                            fixed[y] = edges[x, y]
                        else:
                            fixed[x] = fixed[y] - edges[x, y]
                    else:
                        if fixed[y] is None:
                            fixed[y] = fixed[x] + edges[x, y]
                        else:
                            if fixed[x] + edges[x, y] != fixed[y]:
                                return False
                elif (y, x) in edges:
                    if fixed[y] is None:
                        if fixed[x] is None:
                            fixed[y] = 0
                            fixed[x] = edges[y, x]
                        else:
                            fixed[y] = fixed[x] - edges[y, x]
                    else:
                        if fixed[x] is None:
                            fixed[x] = fixed[y] + edges[y, x]
                        else:
                            if fixed[y] + edges[y, x] != fixed[x]:
                                return False

    xmin = xmax = None
    for i in range(N):
        if fixed[i] is None:
            continue
        if xmin is None:
            xmin = xmax = fixed[i]
        else:
            xmin = min(xmin, fixed[i])
            xmax = max(xmax, fixed[i])
    if xmax is not None and xmin is not None:
        if 10 ** 9 < xmax - xmin:
            return False
    return True


print('Yes' if solve() else 'No')