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: Runtime Error

Solution code:
def main():
  N_PEOPLE, N_INFO = list(map(int, input().split()))

  info_list = []
  for i in range(N_INFO):
    l, r, d = list(map(int, input().split()))
    info_list.append({
      "left":  l-1,
      "right": r-1,
      "dist":  d
    })

  # 各人の位置(不定の場合はNone)
  locations = [None] * N_PEOPLE

  # 各人が登場したか
  appeared = []

  for info in info_list:
    # 左右の人物が共に初登場なら，とりあえずleftを0において，rightを距離の分だけ離す
    if info["left"] not in appeared and info["right"] not in appeared:
      locations[info["left"]] = 0
      locations[info["right"]] = info["dist"]

      appeared.append(info["left"])
      appeared.append(info["right"])

      continue

    # 左の人物だけが初登場なら，rightの人物の位置から見てdist分左におく
    if info["left"] not in appeared and info["right"] in appeared:
      locations[info["left"]] = locations[info["right"]] - info["dist"]

      appeared.append(info["left"])

      continue


    # 右の人物だけが初登場なら，leftの人物から見てdist分右におく
    if info["left"] in appeared and info["right"] not in appeared:
      locations[info["right"]] = locations[info["left"]] + info["dist"]

      appeared.append(info["right"])

      continue

    # 両方の人物が既出なら，距離が正しいかチェックする
    # 正しくなければアウト
    if info["left"] in appeared and info["right"] in appeared:
      if locations[info["right"]] - locations[info["left"]] != info["dist"]:
        print("No")
        return

  max_value = None
  min_value = None

  for location in locations:
    if max_value is None or location > max_value:
      max_value = location

    if min_value is None or location < min_value:
      min_value = location

  if max_value - min_value <= 10**9:
    print("Yes")
  else:
    print("No")

main()

Submission status: Runtime Error

Solution code:
import sys
n,m = map(int,input().split())
a=[]
for i in range(m):
    a.append(list(map(int,input().split())))
for i in range(m):
    for j in range(m):
        if(a[i][1]==a[j][0]):
            dist = a[i][2]+a[j][2]
            for k in range(m):
                
                if(a[k][0]==a[i][0] and a[k][1]==a[j][i]):
                    if(dist != a[k][2]):
                        print("No")
                        sys.exit()
print("Yes")

Submission status: Runtime Error

Solution code:
import sys
N, M = list(map(int, input().split()))

a = []
m = 1000000
for i in range(M):
    l, r, d = list(map(int, input().split()))
    if l > r:
        d = -d
        l,r = r,l
    m = min(m, l)
    a.append(tuple(l,r,d))
a = sorted(a, lambda t: t[0])
d = {}
d[m] = True
p[m] = 0
p = [0 for _ in range(N)]

for i in range(M):
    if (a[i][0] in d) and (a[i][1] in d):
        if ((a[i][1] - a[i][0]) != a[i][2]):
            print('No')
            sys.exit()
    elif (a[i][0] not in d) and (a[i][1] in d):
        np = p[a[i][1]] - a[i][2]
        p[a[i][0]] = np
        d[a[i][0]] = True
    elif (a[i][0] in d) and (a[i][1] not in d):
        np = p[a[i][0]] + a[i][2]
        p[a[i][1]] = np
        d[a[i][1]] = True
    else:
        p[a[i][1]] = 0
        d[a[i][1]] = True

        np = p[a[i][1]] - a[i][2]
        p[a[i][0]] = np
        d[a[i][0]] = True
print('Yes')

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = list(map(int, input().split()))
LRD = []
for i in range(M):
   LRD.append(list(map(int, input().split())))

A = np.zeros([M, N])
AD = np.zeros([M, N+1])
if M != 0:
   for i in range(M):
      A[i][LRD[i][1]-1] = 1
      AD[i][LRD[i][1]-1] = 1
      A[i][LRD[i][0]-1] = -1
      AD[i][LRD[i][0]-1] = -1
      AD[i][N] = LRD[i][2]

   rankA = np.linalg.matrix_rank(A)
   rankAD = np.linalg.matrix_rank(AD)

   if rankA != rankAD:
      print("No")
   else:
      print("Yes")

else:
   print("Yes")

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
distance = np.full((n, n), np.inf)
p = []
for i in range(m):
    l, r, d = map(int, input().split())
    distance[l-1][r-1] = d
    distance[r-1][l-1] = -d
flag = 0
if m > 1:
    for i in range(n-1):
        for j in range(i+1, n-1):
            if distance[i][j] != np.inf and distance[i][j+1] != np.inf and distance[i+1][j+1] != np.inf:
                if distance[i][j] + distance[i+1][j+1] != distance[i][j+1]:
                    flag = 1
                    break
if flag == 0:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
X=[]
for _ in range(M):
    L,R,D=map(int,input().split())
    j = k = None
    for i in range(X):
        if L in X:
            j = i
        if R in X:
            k = i
    if j is None and k is None:
        X.append({L:0, R:D})
    elif j is not None and k is None:
        X[j][R] = X[j][L] + D
    elif j is None:
        X[k][L] = X[k][R] - D
    elif j != k:
        X[j].update(dict([(i,X[k][i]-X[k][R]+X[j][L]+D) for i in X[k].keys()]))
        del X[k]
    elif X[j][R] - X[k][L] != D:
        print("No")
        exit()
print("Yes")

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int,input().split(' '))
X=[[np.inf]*n]*n
i=0
f=0
while i < m:
    l,r,d = map(int,input().split(' '))
    if X[l][r] < 1e+9 and X[l][r] != d:
        f=1
        break
    X[l][r] = d
    i += 1

p=0
while p < n and f==0:
    q=0
    while q < n and f==0:
        r=0
        while r < n and f==0:
            if (X[p][q])<1e+9 and (X[p][r]+X[q][r]) < 1e+9:
                if X[p][q] != X[p][r]+X[q][r]:
                    f=1
                    break
            X[p][q] = min(X[p][q],X[p][r]+X[r][q])
            r+=1
        q+=1
    p+=1
if f==1:
    print('No')
else:print('Yes')

Submission status: Runtime Error

Solution code:
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.push(r)
  return False

def func2():
  lst = Lset-Rset
  for l in lst:
    n[l] = 0
    deq.push(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')

Submission status: Runtime Error

Solution code:
import collections
import heapq

adj = collections.defaultdict(lambda: [])
adji = collections.defaultdict(lambda: [])
L = []

n, m = map(int, input().strip().split(' '))
for i in range(m):
    l, r, d = map(int, input().strip().split(' '))
    l -= 1
    r -= 1
    adj[l].append((r, d))
    adji[r].append((l, d))
    L.append(l)

s = min(L)
dp = collections.defaultdict(lambda: 1000000000000)
dp[s] = 0

q = []
heapq.heappush(q, (dp[s], s))
while len(q) > 0:
    dist, x = heapq.heappop(q)
    for y, d in adj[x]:
        if dist + d < dp[y]:
            dp[y] = dist + d
            heapq.heappush(q, (dp[y], y))

ok = True
for i in range(n):
    for j, d in adj[i]:
        if dp[j] - dp[i] != d:
            ok = False

if ok == True: print("Yes")
else: print("No")

Submission status: Runtime Error

Solution code:
# coding=utf-8

line = input().split(" ")
N = int(line[0])
M = int(line[1])

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

l = []
for _ in range(M):
    line = input().split(" ")
    l.append((
        int(line[0])-1
        ,int(line[1])-1
        ,int(line[2])
    ))
l.sort()
o = l[0][0]
for i in range(M):
    l[i] = (
        l[i][0]-o
        ,l[i][1]-o
        ,l[i][2]
    )

def check(l):
    nl = [None for x in range(N)]
    nl[0] = 0

    flag = True
    while flag:
        flag = False
        ll = []
        for c in l:
            if nl[c[0]]!=None and nl[c[0]]>=0 and nl[c[1]]==None:
                nl[c[1]] = nl[c[0]]+c[2]
            elif nl[c[0]]==None and nl[c[1]]!=None and nl[c[1]]>=0:
                nl[c[0]] = nl[c[1]]-c[2]
            elif nl[c[0]]!=None and nl[c[0]]>=0 and nl[c[1]]!=None and nl[c[1]]>=0:
                if nl[c[1]]-nl[c[0]]==c[2]:
                    pass
                else:
                    print("No")
                    exit()
            else:
                ll.append(c)
                flag = True
        if len(l)==len(ll):
            break
        else:
            l = ll.copy()
    for x in nl:
        if x<0:
            print("No")
            exit()
    return l

while len(l)>0:
    l = check(l)
    if len(l)==0:
        break
    l.sort()
    o = l[0][0]
    for i in range(len(l)):
        l[i] = (
            l[i][0]-o
            ,l[i][1]-o
            ,l[i][2]
        )


print("Yes")

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
distance = np.full((n, n), np.inf)
p = []
for i in range(m):
    l, r, d = map(int, input().split())
    distance[l-1][r-1] = d
    distance[r-1][l-1] = -d
flag = 0
if m > 1:
    for i in range(n-1):
        for j in range(i+1, n-1):
            if distance[i][j] != np.inf and distance[i][j+1] != np.inf and distance[i+1][j+1]:
                if distance[i][j] + distance[i+1][j+1] != distance[i+1][j+1]:
                    flag = 1
                    break
if flag == 0:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
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) ]

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
    if r in LRD:
      if func(r):
        return True
  return False

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

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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
x=[]
a=[0]*N
for i in range(M):
    x.append(list(map(int,input().split())))
sorted(x, key=lambda x:x[0],reverse=True)
if M==0 or M==1:
    print("Yes")
else:
    flag=0
    for i in range(M):
        for j in range(M):
            if i==j:
                continue
            else:
                a[x[j][0]-1]=a[x[j][1]-1]+x[j][2]
        if a[x[j][0]-1]==a[x[j][1]-1]+x[j][2]:
            continue
        else:
            flag=1
            break
if flag==1:
    print("No")
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
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) ]

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
    if func(r):
      return True
  return False

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

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

pars = [None for _ in range(N)]
dists = [0 for _ in range(N)]


def find_root(x, d):
    if pars[x] is None:
        return None, None
    elif pars[x] == x:
        return x, dists[x] + d
    else:
        root, dist_to_root = find_root(pars[x], dists[x])
        pars[x] = root
        dists[x] = dist_to_root + d
        return pars[x], dists[x]


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

    if pars[L] is not None and pars[R] is not None:
        rootL, distL = find_root(L, 0)
        rootR, distR = find_root(R, 0)

        if rootL == rootR:
            if distL + D != distR:
                print('No')
                exit(0)
        else:
            if L < rootR:
                pars[R] = L
                dists[R] = D
            else:
                pars[L] = rootR
                dists[L] = distR - D

    elif pars[L] is not None:
        pars[R] = pars[L]
        dists[R] = D + dists[L]

    elif pars[R] is not None:
        rootR, distR = find_root(R, 0)
        if L < rootR:
            pars[R] = L
            dists[R] = D
        else:
            pars[L] = rootR
            dists[L] = distR - D

    else:
        pars[R] = L
        dists[R] = D

        pars[L] = L
        dists[L] = 0

    # print(pars)
    # print(dists)
    # print()

print('Yes')

Submission status: Runtime Error

Solution code:
import collections

adj = collections.defaultdict(lambda: [])
adji = collections.defaultdict(lambda: [])

n, m = map(int, input().strip().split(' '))
for i in range(m):
    l, r, d = map(int, input().strip().split(' '))
    l -= 1
    r -= 1
    adj[l].append((r, d))
    adji[r].append((l, d))

v = [0] * n
top = []

def dfs(x):
    v[x] = 1
    for r, d in adj[x]:
        if v[r]== 0:
            dfs(r)
    top.append(x)

for i in range(n):
    if v[i] == 0:
        dfs(i)

dp = [100000000] * n
cnt = [0] * n

for i in range(n):
    if len(adji[i]) == 0:
        dp[i] = 0

for x in reversed(top):
    for y, d in adji[x]:
        if dp[y] + d < dp[x]:
            cnt[x] += 1
            dp[x] = dp[y] + d

ok = True
for i in range(n):
    for j, d in adj[i]:
        if dp[j] - dp[i] != d:
            ok = False

if ok == True: print("Yes")
else: print("No")

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split(' '))

LRD = [list(map(int, input().split(' '))) for _ in range(M)]
new_LRD = sorted(LRD, key=lambda x: x[0])

comp = [False] * (N + 1)

cond = True
hold = []

for i in range(M):
    l = new_LRD[i][0]
    r = new_LRD[i][1]
    d = new_LRD[i][2]
    if i == 0:
        comp[l] = 0
        comp[r] = d     
    else:
        if not isinstance(comp[l], bool):
            if isinstance(comp[r], bool):
                  comp[r] = (comp[l] + d)
            else:
                if comp[r] != (comp[l] + d):
                    cond = False
                    break
                    
        else:
            if not isinstance(comp[r], bool):
                comp[l] = (comp[r] - d)
                
            else:
                hold.append([l, r, d])
                

for i in range(len(hold)):
    l = hold[i][0]
    r = hold[i][1]
    d = hold[i][2]    
        if not isinstance(comp[l], bool):
            if isinstance(comp[r], bool):
                  comp[r] = (comp[l] + d)
            else:
                if comp[r] != (comp[l] + d):
                    cond = False
                    break
                    
        else:
            if not isinstance(comp[r], bool):
                comp[l] = (comp[r] - d)
                
            else:
                continue


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

Submission status: Runtime Error

Solution code:
n,m = map(int, raw_input().split())
d=[]
for i in range(m):
   w = map(int, raw_input().split())
   d.append(w)

ok=1

pos=[-1]*(n+1)

pos[d[0][0]]=0
pos[d[0][1]]=d[0][2]

ended=1
ng=0


while ended==1:
   ended=0
   for i in range(1,m):
      if (pos[d[i][0]]<>-1):
         if (pos[d[i][1]]<>-1):
            if (pos[d[i][1]]<>pos[d[i][0]]+d[i][2]) :
               ng=1
               #print i,pos[d[i][1]],pos[d[i][0]],d[i][2]
         else:
            pos[d[i][1]]=pos[d[i][0]]+d[i][2]
      else:
         ended=1
   if ng==1 : break

if ng==1:
   print "No"
else:
   print "Yes"

Submission status: Runtime Error

Solution code:
comp = [False] * (N + 1)

cond = True
hold = []

for i in range(M):
    l = new_LRD[i][0]
    r = new_LRD[i][1]
    d = new_LRD[i][2]
    if i == 0:
        comp[l] = 0
        comp[r] = d     
    else:
        if not isinstance(comp[l], bool):
            if isinstance(comp[r], bool):
                  comp[r] = (comp[l] + d)
            else:
                if comp[r] != (comp[l] + d):
                    cond = False
                    break
                    
        else:
            if not isinstance(comp[r], bool):
                comp[l] = (comp[r] - d)
                
            else:
                hold.append([l, r, d])
                

for i in range(len(hold)):
    l = hold[i][0]
    r = hold[i][1]
    d = hold[i][2]    
        if not isinstance(comp[l], bool):
            if isinstance(comp[r], bool):
                  comp[r] = (comp[l] + d)
            else:
                if comp[r] != (comp[l] + d):
                    cond = False
                    break
                    
        else:
            if not isinstance(comp[r], bool):
                comp[l] = (comp[r] - d)
                
            else:
                continue


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

Submission status: Runtime Error

Solution code:
import collections
from pprint import pprint as pp

N,M = tuple(map(int, input().split()))
#LRD = [tuple(map(int, input().split())) for _ in range(M)]

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

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
    if r in LRD:
      if func(r):
        return True
  return False

def func2():
  lst = Lset-Rset
  for l in lst:
    n[l] = 0
  while lst:
    for l in lst:
      if func(l):
        return True
    Lset2 = set(LRD.keys())
    Rset2 = set(r for r,d in LRD)
    lst = Lset2-Rset2
  lst = tuple(LRD.keys())
  for l in lst:
    if l in LRD:
      if func(l):
        return True
  return False

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
nums={}
ans=True
if m>0:
    l,r,d=input().split()
    nums[l]=1
    nums[r]=1+int(d)

    for p in range(m-1):
        l,r,d=input().split()
        if nums.get(r)==None:
            nums[r]=nums[l]+int(d)
        else:
            if nums[r]!=nums[l]+int(d):
                ans=False
                break

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
nums={}
ans=True
if m>0:
    l,r,d=input().split()
    nums[l]=1
    nums[r]=1+int(d)

    for p in range(m-1):
        l,r,d=input().split()
        if nums.get(r)==None:
            nums[r]=nums[l]+int(d)
        else:
            if nums[r]!=nums[l]+int(d):
                ans=False

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

Submission status: Runtime Error

Solution code:
#-*- coding:utf-8 -*-
import sys

VAL = 100

N, M = map(int, raw_input().split())
arr = []
for i in range(M):
    arr.append(map(int, raw_input().split()))

for i in range(M):
    l = arr[i][0]
    r = arr[i][1]
    d = arr[i][2]
    isr = False
    isl = False
    if r not in dic:
        dic[r] = r
    else:
        key_r = dic[r]
        isr = True
    if l not in dic:
        dic[l] = r - d
    else:
        key_l = dic[l]
        isl = True


    if isr and not isl:
        if key_r - l != d:
            print "No"
            sys.exit()
    elif not isr and isl:
        if r - key_l != d:
            print "No"
            sys.exit()
    elif isr and isl:
        if key_r - key_l != d:
            print "No"
            sys.exit()
    else:
        if r - l != d:
            print "No"
            sys.exit()

print "Yes"

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = list(map(int, input().split()))
LRD = []
for i in range(M):
   LRD.append(list(map(int, input().split())))

A = np.zeros([M, N])
AD = np.zeros([M, N+1])
if M != 0:
   for i in range(M):
      A[i][LRD[i][1]-1] = 1
      AD[i][LRD[i][1]-1] = 1
      A[i][LRD[i][0]-1] = -1
      AD[i][LRD[i][0]-1] = -1
      AD[i][-1] = LRD[i][2]

   rankA = np.linalg.matrix_rank(A)
   rankAD = np.linalg.matrix_rank(AD)

   if rankA != rankAD:
      print("No")
   else:
      print("Yes")

else:
   print("Yes")

Submission status: Runtime Error

Solution code:
#-*- coding:utf-8 -*-
import sys

VAL = 100

N, M = map(int, raw_input().split())
arr = []
for i in range(M):
    arr.append(map(int, raw_input().split()))

dic = {}
l = arr[0][0]
r = arr[0][1]
dic[r] = r
dic[l] = r - arr[0][2]


for i in range(1, M):
    l = arr[i][0]
    r = arr[i][1]
    d = arr[i][2]
    isr = False
    isl = False
    if r not in dic:
        dic[r] = r
    else:
        key_r = dic[r]
        isr = True
    if l not in dic:
        dic[l] = r - d
    else:
        key_l = dic[l]
        isl = True


    if isr and not isl:
        if key_r - l != d:
            print "No"
            sys.exit()
    elif not isr and isl:
        if r - key_l != d:
            print "No"
            sys.exit()
    elif isr and isl:
        if key_r - key_l != d:
            print "No"
            sys.exit()
    else:
        if r - l != d:
            print "No"
            sys.exit()

print "Yes"

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

pars = [None for _ in range(N)]
dists = [0 for _ in range(N)]


def find_root(x, d):
    if pars[x] is None:
        return None, None
    elif pars[x] == x:
        return x, dists[x] + d
    else:
        root, dist_to_root = find_root(pars[x], dists[x])
        pars[x] = root
        dists[x] = dist_to_root + d
        return pars[x], dists[x]


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

    if pars[L] is not None and pars[R] is not None:
        rootL, distL = find_root(L, 0)
        rootR, distR = find_root(R, 0)

        if rootL == rootR:
            if distL + D != distR:
                print('No')
                exit(0)
        else:
            if L < rootR:
                pars[R] = L
                dists[R] = D
            else:
                pars[L] = rootR
                dists[L] = distR - D

    elif pars[L] is not None:
        pars[R] = pars[L]
        dists[R] = D + dists[L]

    elif pars[R] is not None:
        root, dist = find_root(L)
        pars[R] = root
        dists[R] = dist + D

    else:
        pars[R] = L
        dists[R] = D

        pars[L] = L
        dists[L] = 0

    # print(pars)
    # print(dists)
    # print()

print('Yes')

Submission status: Runtime Error

Solution code:
import sys

N, M = map(int, input().split())
L = []
R = []
D = []
for i in range(M):
    k, l, m = map(int, input().split())
    L.append(k)
    R.append(l)
    D.append(m)

DP = [None] * 100001

inc = 0

ids = {}

for i, j, k in sorted(list(zip(L, R, D))):
    if DP[i] != None and DP[j] != None:
        if DP[i][1] != DP[j][1]:
            diff = (DP[i][0] + k) - DP[j][0]
            for l in ids[DP[j][1]]:
                DP[l][0] += diff
                DP[l][1] = DP[l][1]
        if DP[i][1] == DP[j][1] and DP[j][0] != DP[i][0] + k:
            print('No')
            sys.exit()
    if DP[i] == None and DP[j] == None:
        DP[i] = [0, inc]
        DP[j] = [DP[i][0] + k, inc]
        ids[inc] = [i, j]
        inc += 1
    if DP[i] == None and DP[j] != None:
        DP[i] = [DP[j][0] - k, DP[j][1]]
        ids[inc].append(i)
    if DP[i] != None and DP[j] == None:
        DP[j] = [DP[i][0] + k, DP[i][1]]
        ids[inc].appned(j)
    
print('Yes')

Submission status: Runtime Error

Solution code:


import heapq

def dijkstra(nodes, N):
    dist = [float('inf') for i in range(N + 2)]
    prev = [float('inf') for i in range(N + 2)]

    dist[0] = 0
    q = []
    heapq.heappush(q, (0, 0))

    while len(q) != 0:
        prov_cost, src = heapq.heappop(q)
        if dist[src] < prov_cost:
            continue

        for (nextnum, dis) in nodes[src].nextnode:
            cost = dis
            if dist[nextnum] >= dist[src] + cost:
                dist[nextnum] = dist[src] + cost
                heapq.heappush(q, (dist[nextnum], nextnum))
                prev[nextnum] = src
        
    return get_path(N + 1, prev)

def get_path(goal, prev):
    path = [goal]
    dest = goal

    while prev[dest] != float('inf'):
        path.append(prev[dest])
        dest = prev[dest]

    return list(reversed(path))

class People:
    def __init__(self, num):
        self.nodenum = num
        self.nextnode = []

    def set_node(self, num, dis):
        self.nextnode.append((num, dis))

    def node_adj(self):
        if self.nextnode == []:
            self.nextnode.append((self.nodenum + 1, 0))


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

nodes = []
for i in range(N+2):
    nodes.append(People(i))

for i in range(M):
    L, R, D = (int(i) for i in input().split())
    nodes[L].set_node(R, D)

for i in range(N+1):
    nodes[i].node_adj()

ans = dijkstra(nodes, N)

flag = True
for i in range(N+1):
    if ans[i] != i:
        flag = False
if flag:
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = list(map(int, input().split()))
LRD = []
for i in range(M):
   LRD.append(list(map(int, input().split())))

A = np.zeros([M, N])
AD = np.zeros([M, N+1])
for i in range(M):
   A[i][LRD[i][1]-1] = 1
   AD[i][LRD[i][1]-1] = 1
   A[i][LRD[i][0]-1] = -1
   AD[i][LRD[i][0]-1] = -1
   AD[i][-1] = LRD[i][2]

rankA = np.linalg.matrix_rank(A)
rankAD = np.linalg.matrix_rank(AD)

if rankA != rankAD:
   print("No")
else:
   print("Yes")

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
k = [None] * (n+1)
h = []
ans = 'Yes'
for i in range(m):
    l,r,d = map(int,input().split())
    if i == 0: 
        k[l] = 0
        k[r] = d
    else:
        if k[l] is None and k[r] is None:
            h = [(l,r,d)]
        elif k[l] is not None and k[r] is None:
            k[r] = k[l] + d
        elif k[l] is None and k[r] is not None:
            k[l] = k[r] + d
    if k[r] - k[l] != d:
        ans = 'No'
        break

for l,r,d in h:
    if k[l] is None and k[r] is None:
        h = [(l,r,d)]
    elif k[l] is not None and k[r] is None:
        k[r] = k[l] + d
    elif k[l] is None and k[r] is not None:
        k[l] = k[r] + d
    if k[r] - k[l] != d:
        ans = 'No'
        break    
print(ans)

Submission status: Runtime Error

Solution code:
import sys

N, M = map(int, input().split())
L = []
R = []
D = []
for i in range(M):
    k, l, m = map(int, input().split())
    L.append(k)
    R.append(l)
    D.append(m)

DP = [None] * 100001

again = []

for i, j, k in sorted(list(zip(L, R, D))):
    if DP[i] != None and DP[j] != None:
        if DP[j] != DP[i] + k:
            print('No')
            sys.exit()
    if DP[i] == None and DP[j] == None:
        again.append((i,j,k))
        # DP[i] = 0
        # DP[j] = DP[i] + k
    if DP[i] == None and DP[j] != None:
        DP[i] = DP[j] - k
    if DP[i] != None and DP[j] == None:
        DP[j] = DP[i] + k

for i, j, k in again:
        if DP[i] != None and DP[j] != None:
        if DP[j] != DP[i] + k:
            print('No')
            sys.exit()
    if DP[i] == None and DP[j] == None:
        DP[i] = 0
        DP[j] = DP[i] + k
    if DP[i] == None and DP[j] != None:
        DP[i] = DP[j] - k
    if DP[i] != None and DP[j] == None:
        DP[j] = DP[i] + k

print('Yes')

Submission status: Runtime Error

Solution code:
import numpy as np

n, m = map(int, input().split(" "))
l = np.zeros(n, dtype=np.int)
r = np.zeros(n, dtype=np.int)
d = np.zeros(n, dtype=np.int)
for i in range(m):
    l[i], r[i], d[i] = map(int, input().split(" "))

pos = np.zeros(n, dtype=np.int)

for i in range(m):
    if(pos[l[i]-1] == 0 and pos[r[i]-1] == 0):
        pos[l[i]-1] = 1
        pos[r[i]-1] = pos[l[i]-1] + d[i]
    elif(pos[l[i]-1] != 0 and pos[r[i]-1] == 0):
        pos[r[i]-1] = pos[l[i]-1] + d[i]
    elif(pos[l[i]-1] == 0 and pos[r[i]-1] != 0):
        pos[l[i]-1] = pos[r[i]-1] - d[i]
    else:
        if(pos[r[i]-1] - pos[l[i]-1] != d[i]):
            print("No")
            exit()

print("Yes")

Submission status: Runtime Error

Solution code:
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()
    connections[l].add(r)


def solve():
    fixed = [None] * N
    for l, rs in connections.items():
        if fixed[l] is None:
            fixed[l] = 0
        for r in rs:
            if fixed[r] is not None and fixed[l] + edges[l, r] != fixed[r]:
                return False
            elif fixed[r] is None:
                fixed[r] = fixed[l] + edges[l, r]
    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 10 ** 9 < xmax - xmin:
        return False
    return True


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