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: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N,M = map(int,input().split())
    dist = [[] for _ in range(N)]
    
    for i in range(M):
        l,r,d = map(int,input().split())
        dist[l-1].append((r-1,d))
        dist[r-1].append((l-1,-d))
        
    go = [None for _ in range(N)]
    for i in range(N):
        if go[i] is None:
            go[i] = 0
        q = deque([i])
        while q:
            l = q.popleft()
            for r,d in dist[l]:
                if go[r] is None:
                    go[r] = go[l] + d
                else:
                    if go[r] - go[l] != d:
                        print("No")
                        exit()
        
    print("Yes")
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N,M = map(int,input().split())
    dist = [[] for _ in range(N)]
    
    for i in range(M):
        l,r,d = map(int,input().split())
        dist[l-1].append((r-1,d))
        dist[r-1].append((l-1,-d))
        
    go = [None for _ in range(N)]
    for i in range(N):
        if go[i] is None:
            go[i] = 0
        q = deque([i])
        while q:
            l = q.pop()
            for r,d in dist[l]:
                if go[r] is None:
                    go[r] = go[l] + d
                else:
                    if go[r] - go[l] != d:
                        print("No")
                        exit()
        
    print("Yes")
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())

root = [i for i in range(n)]

def find(x):
    return root[x] if root[x] == x else find(root[x])

def union(x,y):
    if find(x) == find(y):
        return
    if find(x) < find(y):
        root[y] = find(x)
    else:
        root[x] = find(y)

g = [[] for _ in range(n)]

from heapq import heappop,heappush
def dist(l,r):
    q = []
    dis = [1234567890] * n
    dis[l] = 0
    heappush(q,(0,l))
    while(q):
        cost, now = heappop(q)
        for ne, ncost in g[now]:
            if dis[ne] > cost + ncost:
                dis[ne] = cost + ncost
                heappush(q,(cost+ncost,ne))
    return dis[r]



for i in range(m):
    l,r,d = map(int,input().split())
    l,r=l-1,r-1
    if find(l) == find(r):
        if d == dist(l,r):
            continue
        else:
            print("No")
            exit()
    else:
        union(l,r)
        g[l].append([r,d])
        g[r].append([l,-d])
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
        # 根への距離を管理
        self.weight = [0] * (n+1)

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y


    def union(self, x, y, w):
        """
        x と y のグループを結合
        """
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
            self.weight[rx] = -w + self.weight[x] - self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]
            self.weight[ry] = w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

     #xからyへのコスト
    def diff(self, x, y):
        return self.weight[y] - self.weight[x]


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

cnt=0
for i in range(M):
    #print(a)
    #print(uf.weight)
    L,R,D=map(int,input().split())
    L-=1
    R-=1

    if uf.is_same(L,R):
        if uf.diff(L,R)!=D:
            print("No")
            exit()
    else:
        uf.union(L,R,D)
        #a[R]=a[L]+D
#print(a)
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def plus(self, x, p):
        x=self.find(x)
        a[x]+=p

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
N,M=map(int,input().split())
uf=UnionFind(N)

a=[0]*N
cnt=0
for i in range(M):
    #print(a)
    L,R,D=map(int,input().split())
    L-=1
    R-=1

    if uf.is_same(L,R):
        if a[L]+D != a[R]:
            print("No")
            exit()
    else:
        p=a[L]+D-a[R]
        uf.plus(R,p)
        uf.union(L,R)
        #a[R]=a[L]+D
#print(a)
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def plus(self, x, p):
        x=self.find(x)
        a[x]+=p

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
N,M=map(int,input().split())
uf=UnionFind(N)

a=[0]*N
cnt=0
for i in range(M):
    #print(a)
    L,R,D=map(int,input().split())
    L-=1
    R-=1

    if uf.is_same(L,R):
        if a[L]+D != a[R]:
            print("No")
            exit()
    else:
        p=a[L]+D
        uf.plus(R,p)
        uf.union(L,R)
        #a[R]=a[L]+D
#print(a)
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y, plus):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        a[y]+=plus
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
N,M=map(int,input().split())
uf=UnionFind(N)

a=[0]*N
cnt=0
for i in range(M):
    #print(a)
    L,R,D=map(int,input().split())
    L-=1
    R-=1

    if uf.is_same(L,R):
        if a[L]+D != a[R]:
            print("No")
            exit()
    else:
        plus=a[L]+D
        uf.union(L,R,plus)
        #a[R]=a[L]+D
#print(a)
print("Yes")

Submission status: Wrong Answer

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

def main():
  n, m = map(int, input().split())
  F = [[] for _ in range(n)]
  lrd = [list(map(int, input().split())) for _ in range(m)]
  for i in range(m):
    l, r, d = lrd[i]
    l -= 1
    r -= 1
    for nr, nd in F[l]:
      if r == nr:
        if d != nd:
          print("No")
          exit()
      else:
        F[nr].append((r, d-nd))
        F[r].append((nr, nd-d))
    F[l].append((r, d))
    for nl, nd in F[r]:
      if l == nl:
        if -d != nd:
          print("No")
          exit()
      else:
        F[l].append((nl, nd+d))
        F[nl].append((l, -nd-d))
    F[r].append((l, -d))
print("Yes")
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

edge = [list(map(int,input().split())) for _ in range(M)]

used = [0 for _ in range(N)]
checked = [0 for _ in range(N)]
inconsistent = False

graph1 = [[] for _ in range(N)]
graph2 = [[] for _ in range(N)]

deg1 = [0 for _ in range(N)]
deg2 = [0 for _ in range(N)]

for e in edge:
    graph1[e[0]-1].append((e[1]-1,e[2]))
    deg1[e[1]-1] += 1
    graph2[e[1]-1].append((e[0]-1,e[2]))
    deg2[e[0]-1] += 1
    used[e[0]-1] = 1
    used[e[1]-1] = 1

root1 = None
root2 = None

for i in range(N):
    if deg1[i] == 0:
        root1 = i
    if deg2[i] == 0:
        root2 = i

if root1 is None or root2 is None:
    print('No')
else:

    stack1 = []
    level1 = [None for _ in range(N)]

    stack1.append(root1)
    level1[root1] = 0
    checked[root1] = 1

    while stack1:
        node = stack1.pop()
        for adj,cost in graph1[node]:
            if not checked[adj]:
                checked[adj] = 1
            if level1[adj] is None:
                level1[adj] = level1[node] + cost
            else:
                if level1[adj] != level1[node] + cost:
                    inconsistent = True
            deg1[adj] -= 1
            if deg1[adj] == 0:
                stack1.append(adj)
        if inconsistent:
            break

    stack2 = []
    level2 = [None for _ in range(N)]

    stack2.append(root2)
    level2[root2] = 0
    checked[root2] = 1

    while stack2:
        node = stack2.pop()
        for adj,cost in graph2[node]:
            if not checked[adj]:
                checked[adj] = 1
            if level2[adj] is None:
                level2[adj] = level2[node] + cost
            else:
                if level2[adj] != level2[node] + cost:
                    inconsistent = True
            deg2[adj] -= 1
            if deg2[adj] == 0:
                stack2.append(adj)
        if inconsistent:
            break

    for i in range(N):
        if used[i] and not checked[i]:
            inconsistent = True
            break

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

Submission status: Wrong Answer

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

edge = [list(map(int,input().split())) for _ in range(M)]

used = [0 for _ in range(N)]
checked = [0 for _ in range(N)]
inconsistent = False

graph1 = [[] for _ in range(N)]
graph2 = [[] for _ in range(N)]

deg1 = [0 for _ in range(N)]
deg2 = [0 for _ in range(N)]

for e in edge:
    graph1[e[0]-1].append((e[1]-1,e[2]))
    deg1[e[1]-1] += 1
    graph2[e[1]-1].append((e[0]-1,e[2]))
    deg2[e[0]-1] += 1
    used[e[0]-1] = 1
    used[e[1]-1] = 1

root1 = None
root2 = None

for i in range(N):
    if deg1[i] == 0:
        root1 = i
    if deg2[i] == 0:
        root2 = i

if root1 is None or root2 is None:
    print('No')
else:

    stack1 = []
    level1 = [None for _ in range(N)]

    stack1.append(root1)
    level1[root1] = 0
    checked[root1] = 1

    while stack1:
        node = stack1.pop()
        for adj,cost in graph1[node]:
            if not checked[adj]:
                checked[adj] = 1
            if level1[adj] is None:
                level1[adj] = level1[node] + cost
            else:
                if level1[adj] != level1[node] + cost:
                    inconsistent = True
            deg1[adj] -= 1
            if deg1[adj] == 0:
                stack1.append(adj)
        if inconsistent:
            break

    stack2 = []
    level2 = [None for _ in range(N)]

    stack2.append(root1)
    level2[root2] = 0
    checked[root2] = 1

    while stack2:
        node = stack2.pop()
        for adj,cost in graph2[node]:
            if not checked[adj]:
                checked[adj] = 1
            if level2[adj] is None:
                level2[adj] = level2[node] + cost
            else:
                if level2[adj] != level2[node] + cost:
                    inconsistent = True
            deg2[adj] -= 1
            if deg2[adj] == 0:
                stack2.append(adj)
        if inconsistent:
            break

    for i in range(N):
        if used[i] and not checked[i]:
            inconsistent = True
            break

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

Submission status: Wrong Answer

Solution code:
import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for l, r, d in zip(*[map(int, sys.stdin.read().split())] * 3):
    graph[l].append((r, d))
    graph[r].append((l, -d))

root = list(range(n+1))
height = [0] * (n + 1)

def find_root(v):
    u = root[v]
    if u == v:
        return u
    w = find_root(u)
    root[v] = w
    return w

def merge(v, u):
    rv = find_root(v)
    ru = find_root(u)
    if rv != ru:
        if height[v] >= height[u]:
            root[ru] = rv
            height[v] = max(height[v], height[v] + 1)
        else:
            root[rv] = ru

def main():
    for v in range(1, n+1):
        for u, d in graph[v]:
            merge(v, u)

    dist = [None] * (n + 1)
    for v in set(root[1:]):
        dist[v] = 0
        stack = [v]
        while stack:
            x = stack.pop()
            for y, d in graph[x]:
                if dist[y] is None:
                    dist[y] = dist[x] + d
                    stack.append(y)
                elif dist[y] != dist[x] + d:
                    return 'No'
    return 'Yes'
      
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
dic = defaultdict(list)
pair = [-1]*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)]
  if pair[l-1]==-1 and pair[r-1]==-1:
    pair[l-1] = 1
    pair[r-1] = 0
  elif pair[l-1]==-1:
    pair[l-1] = 0
  elif pair[r-1]==-1:
    pair[r-1] = 0

dist = [-1]*N
stuck = deque([])
for x in range(N):
  if pair[x]==1:
    stuck += [(x,0)]
    dist[x] = 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: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
dic = defaultdict(list)
pair = [1]*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)]
  pair[min(l-1, r-1)] = 0

dist = [-1]*N
stuck = deque([])
for x in range(N):
  if pair[x]==1:
    stuck += [(x,0)]
    dist[x] = 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: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
dic = defaultdict(list)
pair = [1]*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)]
  pair[r-1] = 0

dist = [-1]*N
stuck = deque([])
for x in range(N):
  if pair[x]==1:
    stuck += [(x,0)]
    dist[x] = 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: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int, input().split(' '))
info = [list(map(int, input().split(' '))) for i in range(m)]
rel = [[] for i in range(n+1)]
p = [10**18 for i in range(n+1)]
for l,r,dist in info:
    rel[l].append((r,dist))
flg=0
for i in range(n):
    if rel[i]!=[]:
        flg+=1
        if flg==1:
            p[i] = 0
        for j in range(len(rel[i])):
            if p[rel[i][j][0]] == 10**18:
                p[rel[i][j][0]] = p[i]+rel[i][j][1]
            elif p[rel[i][j][0]] != p[i]+rel[i][j][1]:
                print("No")
                exit()
            else:
                continue
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    X = [[] for _ in range(N)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        X[l-1].append((r-1, d))
        X[r-1].append((l-1, -d))
    done = [0] * N
    dist = [0] * N
    for i in range(N):
        for j, d in X[i]:
            if done[i]:
                if done[j]:
                    if dist[j] - dist[i] == d:
                        continue
                    else:
                        print("No")
                        return
                else:
                    dist[j] = dist[i] + d
                    done[j] = 1
            else:
                if done[j]:
                    dist[i] = dist[j] - d
                    done[i] = 1
        if done[i] == 0:
            done[i] = 1
    print("Yes")
main()

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    X = [[] for _ in range(N)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        X[l-1].append((r-1, d))
        X[r-1].append((l-1, -d))
    done = [0] * N
    dist = [1<<30] * N
    for i in range(N):
        for j, d in X[i]:
            if done[i]:
                if done[j]:
                    if dist[j] - dist[i] == d:
                        continue
                    else:
                        print("No")
                        return
                else:
                    dist[j] = dist[i] + d
                    done[j] = 1
            else:
                if done[j]:
                    dist[i] = dist[j] - d
                    done[i] = 1
        done[i] = 1
        if dist[i] == 1<<30:
            dist[i] = 0
    print("Yes")
main()

Submission status: Wrong Answer

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
    C[P[a]] += C[P[b]]
    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: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
v=[.1]*(1+n)
for i in range(m):
    l,r,d=map(int,input().split())
    g[l]+=[(r,d)]
    g[r]+=[(l,-d)]
for s in range(1,n+1):
    if v[s]==.1:
        q=[s];v[s]=0
        while q:
            c=q.pop()
            for z,d in g[c]:
                if v[z]==.1:q+=[z];v[z]=v[c]+d
k='Yes'
for i in range(1,n+1):
    for r,d in g[i]:
        if v[l]+d!=v[r]:k='No'
print(k)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for i in range(m):
    l,r,d=map(int,input().split())
    g[l].append((r,d))
    g[r].append((l,-d))
v=[.1]*(1+n)
for s in range(1,n+1):
    if v[s]==.1:
        q=[s];v[s]=0
        while q:
            c=q.pop()
            for z,d in g[c]:
                if v[z]==.1:q+=[z];v[z]=v[c]+d
k='Yes'
for i in range(1,n+1):
    for r,d in g[i]:
        if v[l]+d!=v[r]:k='No'
print(k)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
c=[]
g=[[] for _ in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    l,r=l-1,r-1
    g[l].append((r,d))
    g[r].append((l,-d))
v=[.1]*n
def b(s):
    if v[s]==.1:
        q=[s]
        v[s]=0
        while q:
            c=q.pop()
            for z,d in g[c]:
                if v[z]==.1:
                    q.append(z)
                    v[z]=v[c]+d

for i in range(n):
    b(i)
k='Yes'
for i in range(n):
    for r,d in g[i]:
        if v[l]+d!=v[r]:
            k='No'
print(k)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n,m=LI()
c=[]
x=[inf]*n
ans=True
g=[[] for _ in range(n)]
for i in range(m):
    l,r,d=LI_()
    d+=1
    g[l].append((r,d))
    g[r].append((l,-d))
    c.append((l,r,d))

v=[inf]*n
vs=[-1]*n

def bfs(st):
    if v[st]!=inf:
        return True
    q=[st]
    v[st]=0
    vs[st]=0
    while q:
        
        c=q.pop()
        for nb,d in g[c]:
            if vs[nb]==0:
                continue
            else:
                q.append(nb)
                vs[nb]=0
                if v[nb]==inf:
                    v[nb]=v[c]+d
                elif v[nb]!=v[c]+d:
                    #show(c+1,nb+1,v)
                    return False
    return True

for i in range(n):
    if bfs(i):
        continue
    else:
        print('No')
        exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n,m=LI()
c=[]
x=[inf]*n
ans=True
g=[[] for _ in range(n)]
for i in range(m):
    l,r,d=LI_()
    d+=1
    g[l].append((r,d))
    g[r].append((l,-d))
    c.append((l,r,d))

v=[inf]*n
vs=[-1]*n

def bfs(st):
    if v[st]!=inf:
        return True
    q=[st]
    v[st]=0
    vs[st]=0
    while q:
        
        c=q.pop()
        for nb,d in g[c]:
            if vs[nb]==0:
                continue
            else:
                if v[nb]!=inf:
                    q.append(nb)
                    v[nb]=v[c]+d
                elif v[nb]+d!=v[c]:
                    return False
    return True

for i in range(n):
    if bfs(i):
        continue
    else:
        print('No')
        exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n,m=LI()
c=[]
x=[inf]*n
ans=True
for i in range(m):
    l,r,d=LI_()
    d+=1
    if x[l]==inf and x[r]==inf:
        x[l],x[r]=0,d
    elif x[l]!=inf and x[r]!=inf:
        if x[r]-x[l]!=d:
            ans=False
            break
    elif x[l]!=inf and x[r]==inf:
        x[r]=x[l]+d
    elif x[l]==inf and x[r]!=inf:
        x[l]=x[r]-d
    
print(YN[1-ans])

Submission status: Wrong Answer

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

info=sorted(info,key=lambda x:x[0])
L,R,d=info[0]
dist[L]=0
dist[R]=d

for i in range(1,len(info)):
  L,R,d=info[i]
  if dist[L]==INF and dist[R]==INF:
    print("No")
    break
  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: Wrong Answer

Solution code:
n,m = map(int,input().split())

a = []
dic = {}
for _ in range(m):
    l,r,d = map(int,input().split())
    a.append((l,r,d))
    if l not in dic and r not in dic:
        dic[l] = 0
        dic[r] = d
    elif r not in dic:
        dic[r] = dic[l] + d
    elif l not in dic:
        dic[l] = dic[r] - d
    else:
        if dic[r] - dic[l] != d:
            print("No")
            import sys
            sys.exit()

for l,r,d in a:
    if dic[r] - dic[l] != d:
        print("No")
        import sys
        sys.exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())

dic = {}
for _ in range(m):
    l,r,d = map(int,input().split())
    if l not in dic and r not in dic:
        dic[l] = 0
        dic[r] = d
    elif r not in dic:
        dic[r] = dic[l] + d
    elif l not in dic:
        dic[l] = dic[r] - d
    else:
        if dic[r] - dic[l] != d:
            print("No")
            import sys
            sys.exit()
print("Yes")