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



Sample input:
3 3
1 2 1
2 3 1
1 3 2


Sample output:
Yes

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
q = [list(map(int, input().split())) for i in range(m)]

g = [[] for i in range(n+1)]

for i in range(m):
    a, b, c = q[i]
    g[a].append((b, c))
    g[b].append((a, -c))

people = [-10**10] * (n+1)

flag = 1
for i in range(1, n+1):
    if people[i] != -10**10:
        continue
    q = [i]
    while q:
        now = q.pop()
        for next, dist in g[now]:
            if people[next] == -10**10:
                q.append(next)
                people[next] = people[now] + dist
            else:
                if people[next] == people[now] + dist:
                    continue
                else:
                    flag = 0
                    break
        if flag == 0:
            break

if max(people[1:]) - min(people[1:]) > 10**9:
    flag = 0
    
if flag == 1:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


N, M = map(int, input().split())


# In[2]:


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


# In[3]:


def func():
    houmon = [False] * N

    for start in range(N):
        x = [0] * N
        if houmon[start]:
            continue
        stack = [start]
        while stack:
            n1 = stack.pop()
            houmon[n1] = True
            for n2, d in link[n1]:
                if houmon[n2]:
                    if x[n2] != x[n1] + d:
                        return False
                else:
                    x[n2] = x[n1] + d
                    stack.append(n2)
        
#         if max(x) - min(x) > 10 ** 9:
#             return False
    
    return True


# In[4]:


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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[27]:


N, M = map(int, input().split())


# In[28]:


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


# In[24]:


link


# In[25]:


def func():
    x = [0] * N
    houmon = [False] * N

    for start in range(N):
        if houmon[start]:
            continue
        stack = [start]
        while stack:
            n1 = stack.pop(0)
            houmon[n1] = True
            for n2, d in link[n1]:
                if houmon[n2]:
                    if x[n2] != x[n1] + d:
                        return False
                else:
                    x[n2] = x[n1] + d
                    stack.append(n2)
    
    return max(x) - min(x) <= 10 ** 9
    


# In[26]:


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


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys

readline = sys.stdin.buffer.readline

N, M = map(int, readline().split())
dic = defaultdict(list)
par = [i for i in range(N)]
rank = [0]*N
def find(x):
  if par[x]==x:
    return x
  else:
    par[x] = find(par[x])
    return par[x]
def unit(x, y):
  x = find(x)
  y = find(y)
  if x==y:
    return
  elif rank[x]<rank[y]:
    par[x] = y
    return
  elif rank[y]<rank[x]:
    par[y] = x
  else:
    par[y] = x
    rank[x] += 1

for i in range(M):
  l, r, d = map(int, readline().split())
  dic[l-1] += [(r-1,d)]
  dic[r-1] += [(l-1,-d)]
  unit(l-1, r-1)


dist = [-1]*N
m = []
for x in range(N):
  y = find(x)
  m += [(y,0)]
  dist[y] = 0
m = set(m)
stuck = deque(m)
while stuck:
  e, a = stuck.popleft()
  flag = False
  for c in dic[e]:
    p, d = c
    x = d + dist[e]
    if dist[p]==-1:
      dist[p] = x
      stuck += [(p, x)]
    elif dist[p]!=x:
      print('No')
      flag = True
      break
  if flag:
    break
else:
  print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys

readline = sys.stdin.buffer.readline

N, M = map(int, readline().split())
dic = defaultdict(list)
par = [i for i in range(N)]
rank = [0]*N
def find(x):
  if par[x]==x:
    return x
  else:
    par[x] = find(par[x])
    return par[x]
def unit(x, y):
  x = find(x)
  y = find(y)
  if x==y:
    return
  elif rank[x]<rank[y]:
    par[x] = y
    return
  elif rank[y]<rank[x]:
    par[y] = x
  else:
    par[y] = x
    rank[x] += 1

for i in range(M):
  l, r, d = map(int, readline().split())
  dic[l-1] += [(r-1,d)]
  dic[r-1] += [(l-1,-d)]
  unit(l-1, r-1)


dist = [-1]*N
for x in range(N):
  x = find(x)
par = set(par)
stuck = deque([])
for c in par:
  stuck += [(c,0)]
  dist[c] = 0
while stuck:
  e, a = stuck.popleft()
  flag = False
  for c in dic[e]:
    p, d = c
    x = d + dist[e]
    if dist[p]==-1:
      dist[p] = x
      stuck += [(p, x)]
    elif dist[p]!=x:
      print('No')
      flag = True
      break
  if flag:
    break
else:
  print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
    self.P = [1]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.P[x] = 0
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.P[y] = 0
    else:
      self.par[y] = x
      self.P[y] = 0
      self.rank[x] += 1
      

N, M = map(int, input().split())
dic = defaultdict(list)
union = UnionFind(N)

for i in range(M):
  l, r, d = map(int, input().split())
  dic[l-1] += [(r-1,d)]
  dic[r-1] += [(l-1,-d)]
  union.unit(l-1, r-1)

dist = [-1]*N
pair = []
for x in range(N):
  if union.P[x]==1:
    pair += [(x,0)]
    dist[x] = 0

stuck = deque(pair)
while stuck:
  e, a = stuck.popleft()
  flag = False
  for c in dic[e]:
    p, d = c
    x = d + dist[e]
    if dist[p]==-1:
      dist[p] = x
      stuck += [(p, x)]
    elif dist[p]!=x:
      print('No')
      flag = True
      break
  if flag:
    break
else:
  print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
    self.P = [1]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.P[x] = 0
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.P[y] = 0
    else:
      self.par[y] = x
      self.P[y] = 0
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  

N, M = map(int, input().split())
dic = defaultdict(list)
union = UnionFind(N)

for i in range(M):
  l, r, d = map(int, input().split())
  dic[l-1] += [(r-1,d)]
  dic[r-1] += [(l-1,-d)]
  union.unit(l-1, r-1)

pair = []
for x in range(N):
  if union.P[x]==1:
    pair += [x]

dist = [-1]*N
for c in pair:
  stuck = deque([(c,0)])
  dist[c] = 0
  while stuck:
    e, a = stuck.popleft()
    flag = False
    for c in dic[e]:
      p, d = c
      x = d + dist[e]
      if dist[p]==-1:
        dist[p] = x
        stuck += [(p, x)]
      elif dist[p]!=x:
        print('No')
        flag = True
        break
    if flag:
      break
  if flag:
    break
else:
  print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
    self.P = [1]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.P[x] = 0
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.P[y] = 0
    else:
      self.par[y] = x
      self.P[y] = 0
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  

N, M = map(int, input().split())
dic = defaultdict(list)
union = UnionFind(N)

for i in range(M):
  l, r, d = map(int, input().split())
  dic[l-1] += [(r-1,d)]
  dic[r-1] += [(l-1,-d)]
  union.unit(l-1, r-1)

pair = []
for x in range(N):
  if union.P[x]==1:
    pair += [x]

dist = [-1]*N
for c in pair:
  stuck = deque([(c,0)])
  dist[c] = 0
  while stuck:
    e, a = stuck.popleft()
    for c in dic[e]:
      p, d = c
      x = d + dist[e]
      if dist[p]==-1:
        dist[p] = x
        stuck += [(p, x)]
      elif dist[p]!=x:
        print('No')
        sys.exit()
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.size = [1]*n
    self.rank = [0]*n
    self.P = [1]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.P[x] = 0
      self.size[y] += self.size[x]
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.P[y] = 0
      self.size[x] += self.size[y]
    else:
      self.par[y] = x
      self.P[y] = 0
      self.size[x] += self.size[y]
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
  def count(self, x):
    return self.size[x]

N, M = map(int, input().split())
dic = defaultdict(list)
union = UnionFind(N)

for i in range(M):
  l, r, d = map(int, input().split())
  dic[l-1] += [(r-1,d)]
  dic[r-1] += [(l-1,-d)]
  union.unit(l-1, r-1)

pair = []
for x in range(N):
  if union.P[x]==1:
    pair += [x]

dist = [-1]*N
for c in pair:
  stuck = deque([(c,0)])
  dist[c] = 0
  while stuck:
    e, a = stuck.popleft()
    flag = False
    for c in dic[e]:
      p, d = c
      x = d + dist[e]
      if dist[p]==-1:
        dist[p] = x
        stuck += [(p, x)]
      elif dist[p]!=x:
        print('No')
        flag = True
        break
    if flag:
      break
  if flag:
    break
else:
  print('Yes')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
P = [i for i in range(N)]
D = [0] * N
C = [1] * N

def par(a):
    if a == P[a]:
        return a
    p = par(P[a])
    d = D[P[a]]
    P[a] = p
    D[a] += d
    return p

def dist(a, b):
    pa = par(a)
    pb = par(b)
    if pa == pb:
        return D[b] - D[a]
    return 1 << 30

def unite(a, b, d):
    if par(a) == par(b):
        return
    if C[P[a]] < C[P[b]]:
        a, b = b, a
    D[P[b]] = D[a] + d - D[b]
    P[P[b]] = P[a]

for _ in range(M):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    dd = dist(l, r)
    if dd == 1<<30:
        unite(l, r, d)
    else:
        if d != dd:
            print("No")
            break
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
P = [i for i in range(N)]
D = [0] * N

def par(a):
    if a == P[a]:
        return a
    p = par(P[a])
    d = D[P[a]]
    P[a] = p
    D[a] += d
    return p

def dist(a, b):
    pa = par(a)
    pb = par(b)
    if pa == pb:
        return D[b] - D[a]
    return 1 << 30

def unite(a, b, d):
    if par(a) == par(b):
        return
    D[P[b]] = D[a] + d - D[b]
    P[P[b]] = P[a]

for _ in range(M):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    dd = dist(l, r)
    if dd == 1<<30:
        unite(l, r, d)
    else:
        if d != dd:
            print("No")
            break
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)

n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

graph = {j:[] for j in range(n)}
for i in range(m):
    l, r, d = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    graph[l].append((r, d))
    graph[r].append((l, -d))

yet = set(list(range(n)))
x_ls = [None for i in range(n)]
x_ls[0] = 0
que = deque([0])
flg = True
while len(que) > 0:
    cur = que.popleft()
    if cur in yet:
        yet.remove(cur)
    cur_pos = x_ls[cur]
    for _next, dis in graph[cur]:
        if x_ls[_next] is None:
            x_ls[_next] = cur_pos + dis
            que.append(_next)
        else:
            if x_ls[_next] != cur_pos + dis:
                flg = False
                break
    if not flg:
        break
    if len(que) == 0 and len(yet) > 0:
        root = list(yet)[0]
        que.append(root)
        x_ls[root] = 0
        yet.remove(root)
if flg:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
n, m = [int(i) for i in sys.stdin.readline().split()]
dis_dict = dict()
parent = [i for i in range(n)]

def find_root(a):
    ls = []
    while parent[a] != a:
        ls.append(a)
        a = parent[a]
    for l in ls:
        parent[l] = a
    return a

def is_same(a, b):
    root_a = find_root(a)
    root_b = find_root(b)
    return root_b == root_a

def unite(a, b):
    root_a = find_root(a)
    root_b = find_root(b)
    if root_a != root_b:
        parent[root_b] = root_a

graph = {j:[] for j in range(n)}
for i in range(m):
    l, r, d = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    unite(l, r)
    graph[l].append((r, d))
    graph[r].append((l, -d))

yet = list(range(n))
x_ls = [None for i in range(n)]
x_ls[0] = 0
que = deque([0])
flg = True
while len(que) > 0:
    cur = que.popleft()
    if cur in yet:
        yet.remove(cur)
    cur_pos = x_ls[cur]
    for _next, dis in graph[cur]:
        if x_ls[_next] is None:
            x_ls[_next] = cur_pos + dis
            que.append(_next)
        else:
            if x_ls[_next] != cur_pos + dis:
                flg = False
                break
    if not flg:
        break
    if len(que) == 0 and len(yet) > 0:
        que.append(yet[0])
        x_ls[yet[0]] = 0
        yet.pop(0)
if flg:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
n, m = [int(i) for i in sys.stdin.readline().split()]
dis_dict = dict()
parent = [i for i in range(n)]

def find_root(a):
    ls = []
    while parent[a] != a:
        ls.append(a)
        a = parent[a]
    for l in ls:
        parent[l] = a
    return a

def is_same(a, b):
    root_a = find_root(a)
    root_b = find_root(b)
    return root_b == root_a

def unite(a, b):
    root_a = find_root(a)
    root_b = find_root(b)
    if root_a != root_b:
        parent[root_b] = root_a

graph = {j:[] for j in range(n)}
for i in range(m):
    l, r, d = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    unite(l, r)
    graph[l].append((r, d))
    graph[r].append((l, -d))

roots = [find_root(i) for i in range(n)]
x_ls = [None if i not in roots else 0 for i in range(n)]
que = deque(list(set(roots)))
flg = True
while len(que) > 0:
    cur = que.popleft()
    cur_pos = x_ls[cur]
    for _next, dis in graph[cur]:
        if x_ls[_next] is None:
            x_ls[_next] = cur_pos + dis
            que.append(_next)
        else:
            if x_ls[_next] != cur_pos + dis:
                flg = False
                break
    if not flg:
        break
if flg:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
dis_dict = dict()
parent = [i for i in range(n)]

def calc_dis(x):
    ls = []
    cnt = 0
    while parent[x] != x:
        ls.append(x)
        cnt += dis[x]
        x = parent[x]
    for l in ls:
        parent[l] = x
    return cnt

graph = [[0 for i in range(n)] for j in range(n)]
dis = [0 for i in range(n)]
already = set()
flg = True
for i in range(m):
    l, r, d = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    if l in already and r in already:
        if calc_dis(r) - calc_dis(l) != d:
            flg = False
            break
    if r in already:
        if dis[r] > d:
            parent[l] = parent[r]
            dis[l] = dis[r] - d
            dis[r] = d
        else:
            parent[parent[r]] = l
            dis[parent[r]] = d - dis[r]
    else:
        parent[r] = l
        dis[r] = d
    already.update((l, r))
if flg:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[False]*n
g=[[] for _ in [0]*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))
for i in range(n):
    if not(a[i]):
        a[i]=0
        q=[i]
    while q:
        j=q.pop()
        for x,e in g[j]:
            if not(a[x]):
                a[x]=a[j]+e
                q.append(x)
            elif a[x]!=a[j]+e:
                print("No")
                exit()
                
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[False]*n
g=[[] for _ in [0]*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))
for i in range(n):
    if not(a[i]):
        a[i]=0
        q=[i]
    while q:
        j=q.pop()
        for x,e in g[j]:
            if not(a[x]):
                a[x]=a[j]+e
                q.append(x)
            elif a[x]!=a[j]+e:
                print("No")
                exit()
                
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[False]*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))
for i in range(n):
    if not(a[i]):
        a[i]=0
        q=[i]
    while q:
        j=q.pop()
        for x,e in g[j]:
            if not(a[x]):
                a[x]=a[j]+e
                q.append(x)
            elif a[x]!=a[j]+e:
                print("No")
                exit()
                
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
if M==0:
  print("Yes")
  exit(0)
INF=10**9+1
dist=[INF]*N
from collections import deque
info=deque()
for i in range(M):
  L,R,d=map(int,input().split())
  L,R=L-1,R-1
  info.append([L,R,d])
  
L,R,d=info.popleft()
dist[L]=0
dist[R]=d

while info:
  L,R,d=info.popleft()
  if dist[L]==INF and dist[R]==INF:
    info.append([L,R,d])
  else:
    if dist[L]!=INF and dist[R]==INF:
      dist[R]=dist[L]+d
    elif dist[L]==INF and dist[R]!=INF:
      dist[L]=dist[R]-d
    else:
      if dist[L]+d!=dist[R]:
        print("No")
        exit(0)
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
if M==0:
  print("Yes")
  exit(0)
INF=10**9+1
dist=[INF]*N
info=[None]*M
for i in range(M):
  L,R,d=map(int,input().split())
  L,R=L-1,R-1
  info[i]=[L,R,d]
  
checked=[False]*M
L,R,d=info[0]
checked[0]=True
dist[L]=0
dist[R]=d

def ifNotFinished():
  for c in checked:
    if c==False:
      return True
while ifNotFinished():
  for i in range(len(info)):
    if not checked[i]:
      L,R,d=info[i]
      if dist[L]==INF and dist[R]==INF:
        continue
      else:
        if dist[L]!=INF and dist[R]==INF:
          dist[R]=dist[L]+d
        elif dist[L]==INF and dist[R]!=INF:
          dist[L]=dist[R]-d
        else:
          if dist[L]+d!=dist[R]:
            print("No")
            exit(0)
      checked[i]=True
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
#87D cleaned …確実にLTE食らう
N,M = map(int, input().split())

#iの番号を合わせるのに、最初に不要だけど、値を入れておく。
L_list=[0]
R_list=[0]
D_list=[0]

#LRD_listを初期化
#[n][0]:値入力済みのもののset　、　[n][m (m>0)]:n→mの変位
LRD_list = [["?"] * (N+1) for i in range(N+1)]
for i in range(N+1):
    LRD_list[i][0] = set()
    LRD_list[i][i] = 0 #自分→自分の変位は0

for i in range(1,M+1): #M < 2*10**5
    #print("#########################")
    L,R,D = map(int, input().split())
    
    if LRD_list[L][R] == "?" or  LRD_list[L][R] == D:
        if  LRD_list[L][R] == "?":
            LRD_list[L][R] = D
            LRD_list[R][L] = -D
            
            #print(L,"→",R,":",D)
            #print(R,"→",L,":",-D)
            
            for j in LRD_list[L][0]:
                LRD_list[R][j] = -D + LRD_list[L][j] #R→L→j
                LRD_list[R][0].add(j)
                LRD_list[j][R] = - LRD_list[L][j] + D #j→L→R
                LRD_list[j][0].add(R)
                
                #print(R,"→",j,":",- LRD_list[L][R] + LRD_list[L][j])
                #print(j,"→",R,":",- LRD_list[L][j] + LRD_list[L][R])
                
            LRD_list[L][0].add(R)
            
            for j in LRD_list[R][0]:
                LRD_list[L][j] = D + LRD_list[R][j] #L→R→j
                LRD_list[L][0].add(j)
                LRD_list[j][L] = - LRD_list[R][j] -D #j→R→L
                LRD_list[j][0].add(L)
                
                #print(L,"→",j,":",- LRD_list[R][L] + LRD_list[R][j])
                #print(j,"→",L,":",- LRD_list[R][j] + LRD_list[R][L])
                
            LRD_list[R][0].add(L)              
    else: # LRD_list[L][R] != "?" and  LRD_list[L][R] != D
        #print(L,"→",R,"=",LRD_list[L][R],".Not ",D)
        print("No")
        break
else:
    print("Yes")

#print("final:LRD_list")
#print(LRD_list)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v,w=map(int,input().split())
        u-=1; v-=1
        E[v].append((u,w))
    # dfsで各連結成分毎に最長経路を計算していく
    # 仮に更新されるようなことがあれば矛盾
    dist=[INF]*n
    visited=[0]*n
    def dfs(v)->bool:
        d=0
        flag=False
        visited[v]=1
        for nv,w in E[v]:
            # ループ検出
            if(visited[nv] and dist[nv]==INF):
                return False
            # nv の最長経路を計算
            if(not dfs(nv)):
                return False
            else:
                if(not flag):
                    d=dist[nv]+w
                    flag=True
                else:
                    if(d!=dist[nv]+w):
                        return False
        dist[v]=d
        return True
    print("Yes" if(all(dfs(v) for v in range(n))) else "No")
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

n,m=map(int,input().split())
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*(-1)])
f=[False for _ in range(n)]

def dfs(s,x):
    f[s] = x
    for sg in g[s]:
        if type(f[sg[0]]) == bool:
            if not dfs(sg[0],sg[1]+x):
                return False
        else:
            if f[sg[0]] - f[s] != sg[1]:
                return False
    return True

def main():
    for i in range(n):
        if type(f[i]) == bool:
            if not dfs(i,1):
                return "No"
    return "Yes"

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

n,m=map(int,input().split())
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*(-1)])
INF = 10**10
f=[INF for _ in range(n)]

def dfs(s,x):
    f[s] = x
    for sg in g[s]:
        if f[sg[0]] == INF:
            if not dfs(sg[0],sg[1]+x):
                return False
        else:
            if f[sg[0]] - f[s] != sg[1]:
                return False
    return True

def main():
    for i in range(n):
        if f[i] == INF:
            if not dfs(i,0):
                return "No"
    return "Yes"

print(main())

Submission status: Time Limit Exceeded

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

N, M = map(int, readline().split())

if M == 0:
    print('Yes')
    exit()

LRD = map(int, read().split())
graph = [[] for _ in range(N + 1)]

# 根からの距離、根は複数の可能性あり
distance = [-1] * (N + 1)
child = [0] * (N + 1)

for L, R, D in zip(LRD, LRD, LRD):
    graph[L].append((R, D))
    child[R] += 1

for i in range(1, N + 1):
    if child[i]:
        continue

    # 以下iは根
    distance[i] = 0
    stack = [i]
    while stack:
        V = stack.pop()
        for v, d in graph[V]:
            if distance[v] == -1:
                distance[v] = distance[V] + d
            else:
                if distance[v] != distance[V] + d:
                    print('No')
                    exit()

            stack.append(v)

# 例4のような循環タイプは上のfor内で処理されない
if -1 in distance[1:]:
    print('No')
else:
    print('Yes')

Submission status: Time Limit Exceeded

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


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

    if M == 0:
        print('Yes')
        exit()

    *LRD, = map(int, read().split())
    graph = [[] for _ in range(N + 1)]

    # 根からの距離、根は複数の可能性あり
    distance = [-1] * (N + 1)
    child = [0] * (N + 1)

    for L, R, D in zip(*[iter(LRD)] * 3):
        graph[L].append((R, D))
        child[R] += 1

    for i in range(1, N + 1):
        if child[i]:
            continue

        # 以下iは根
        distance[i] = 0
        stack = [i]
        while stack:
            V = stack.pop()
            for v, d in graph[V]:
                if distance[v] == -1:
                    distance[v] = distance[V] + d
                else:
                    if distance[v] != distance[V] + d:
                        print('No')
                        exit()

                stack.append(v)

    # 例4のような循環タイプは上のfor内で処理されない
    if -1 in distance[1:]:
        print('No')
    else:
        print('Yes')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N, M = map(int, readline().split())

if M == 0:
    print('Yes')
    exit()

*LRD, = map(int, read().split())
graph = [[] for _ in range(N + 1)]

# 根からの距離、根は複数の可能性あり
distance = [-1] * (N + 1)
child = [0] * (N + 1)

for L, R, D in zip(*[iter(LRD)] * 3):
    graph[L].append((R, D))
    child[R] = 1

for i in range(1, N + 1):
    if child[i]:
        continue

    # 以下iは根
    distance[i] = 0
    stack = [i]
    while stack:
        V = stack.pop()
        for v, d in graph[V]:
            if distance[v] == -1:
                distance[v] = distance[V] + d
            else:
                if distance[v] != distance[V] + d:
                    print('No')
                    exit()

            stack.append(v)

# 例4のような循環タイプは上のfor内で処理されない
if -1 in distance[1:]:
    print('No')
else:
    print('Yes')

Submission status: Time Limit Exceeded

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

N, M = map(int, readline().split())

if M == 0:
    print('Yes')
    exit()

*LRD, = map(int, read().split())
graph = [[] for _ in range(N + 1)]

# 根からの距離、根は複数の可能性あり
distance = [-1] * (N + 1)
child = [False] * (N + 1)

for L, R, D in zip(*[iter(LRD)] * 3):
    graph[L].append((R, D))
    child[R] = True

for i in range(1, N + 1):
    if child[i]:
        continue

    # 以下iは根
    distance[i] = 0
    stack = [i]
    while stack:
        V = stack.pop()
        for v, d in graph[V]:
            if distance[v] == -1:
                distance[v] = distance[V] + d
            else:
                if distance[v] != distance[V] + d:
                    print('No')
                    exit()

            stack.append(v)

# 例4のような循環タイプは上のfor内で処理されない
if -1 in distance[1:]:
    print('No')
else:
    print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li[l].append((r,d))
		li[r].append((l,-d))
	
	q=deque()
	a=[None]*(n+1)

	for i in range(1,n+1):
		if a[i]==None:
			q=[i]
			a[i]=0
			while q:
				now=q.pop()
				for r,d in li[now]:
					if r in q:
						if a[r]-a[now]!=d:
							print("No")
							exit(0)
						else:
							continue
					else:
						a[r] = a[now] + d
						q.append(r)
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()