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:
class UF_weighed:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n+1))
        self.rank = [0]*(n+1)
        self.size = [1]*(n+1)
        self.diff_w = [0]*(n+1)

    def find(self, x):
        if self.par[x] == x: return x
        p = self.find(self.par[x])
        self.diff_w[x] += self.diff_w[self.par[x]]
        self.par[x] = p
        return self.par[x]

    def weight(self, x):
        self.find(x)
        return self.diff_w[x]

    def diff(self, x, y):
        if not self.same(x, y): return None
        return self.weight(y) - self.weight(x)

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def merge(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y, w = y, x, -w
        self.par[y] = x
        self.size[x] += self.size[y]
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.diff_w[y] = w
        return True

n,m = map(int, input().split())
uf = UF_weighed(n+1)
for _ in range(m):
  a, b, c = map(int, input().split())
  if uf.same(a, b) and uf.diff(a, b) != c:
    print('No')
    break
  uf.merge(a, b, c)
else:
  print('Yes')

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index):
        if self.parent[index] == index:  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2):  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2:  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2]:
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else:
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2]:
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2):
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index):
        return self.size[self.root(index)]

    def getComponent(self):
        return self.component

N, M = map(int, input().split())
INF = 10**18
tree = UnionFind(N)

edges = [[] for _ in range(N)]
degree = [0] * N
for _ in range(M):
    fr, to, d = map(int, input().split())
    fr -= 1
    to -= 1
    edges[to].append((fr, d))
    degree[fr] += 1
    tree.union(fr, to)

D = [INF] * N
for i in range(N):
    D[tree.root(i)] = min(D[tree.root(i)], degree[i])

if max([D[i] for i in range(N) if tree.root(i) == i]) != 0:
    print('No')
    exit()

V = set()
for start in range(N):
    if degree[start] > 0:
        continue
    minDist = [INF] * N
    st = [(start, 0)]
    W = set()
    while st:
        now, dist = st.pop()
        W.add(now)

        if minDist[now] == dist:
            continue

        if minDist[now] != INF and minDist[now] != dist:
            print('No')
            exit()

        minDist[now] = dist
        for to, d in edges[now]:
            if minDist[to] == d + dist or to in V:
                continue
            st.append((to, dist + d))
    V |= W

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import heapq 
n, m = map(int, input().split())
if m == 0:
    print('Yes')
    exit()
lrd = [list(map(int, input().split())) for _ in range(m)]
lrd.sort()
di = {i:'?' for i in range(n+1)}
di[lrd[0][0]] = 0

while lrd:
    l, r, d = lrd.pop(0)
    if di[l] == '?' and di[r] == '?':
        lrd += [[l, r, d]]
    elif di[l] != '?' and di[r] == '?':
        di[r] = di[l] + d  
    elif di[l] == '?' and di[r] != '?':
        di[l] = di[r] - d 
    else:
        if di[l] + d != di[r]:
            print('No')
            exit()

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import heapq 
n, m = map(int, input().split())
if m == 0:
    print('Yes')
    exit()
lrd = [list(map(int, input().split())) for _ in range(m)]
heapq.heapify(lrd)
di = {i:'?' for i in range(n+1)}
di[lrd[0][0]] = 0
while lrd:
    l, r, d = heapq.heappop(lrd)
    if di[l] == '?' and di[r] == '?':
        heapq.heappush(lrd, [l, r, d])
    elif di[l] != '?' and di[r] == '?':
        di[r] = di[l] + d  
    elif di[l] == '?' and di[r] != '?':
        di[l] = di[r] - d 
    else:
        if di[l] + d != di[r]:
            print('No')
            exit()

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
#PyPy遅え
import sys
sys.setrecursionlimit(400000000)
inf=1000000000000000000
n,m=map(int,input().split())
x=[inf]*n
#まだ訪問してなければTrue
check=[True]*n
#どこと関係があるかを記録する(maybe right)
lrd=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    lrd[l].append((r,d))
    lrd[r].append((l,-d))
#wrong thought
#どっちも決まってない場合の処理
#決まってるとこからやれば良い
#ソートして順番に決めておく

#記録した関係から辿っていく
#まず初めのやつ決定
#非連結な場合を忘れていた

f=False
def bfs(z):
    #globalくらいちゃんとしろ
    global lrd,check,x,f
    if f:return
    for i in range(len(lrd[z])):
        k=lrd[z][i]
        if check[k[0]]:
            x[k[0]]=x[z]+k[1]
            check[k[0]]=False
            bfs(k[0])
        else:
            if x[k[0]]!=x[z]+k[1]:
                f=True
                return
st=0
while any(check):
    for i in range(st,n):
        if len(lrd[i])!=0 and check[i]:
            st=i
            break
        else:
            check[i]=False
    else:
        break
    x[st]=0
    check[st]=False
    bfs(st)
    #print(check)
if f:
    print("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split(' '))
graph = [[] for _ in range(N)]
for i in range(M):
    l, r, d = map(int, input().split(' '))
    l -= 1
    r -= 1
    graph[l].append((r, d))
    graph[r].append((l, -d))

dsts = [float('inf') for _ in range(N)]

for n in range(N):
    if dsts[n] != float('inf'):
        continue

    buf = [n]
    dsts[n] = 0
    while buf:
        src = buf.pop(0)
        for dst, d, in graph[src]:
            next_d = dsts[src] + d

            if dsts[dst] == float('inf'):
                dsts[dst] = next_d
                buf.append(dst)

            elif dsts[dst]  != next_d:
                # print(dsts)
                # print(dst, src, dsts[dst], dsts[src], d, next_d)
                print("No")
                exit()

print("Yes")

Submission status: Time Limit Exceeded

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

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

graph = [[] for i in range(N)]
dis = [[None]*N for i in range(N)]

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

data = [None]*N

for i in range(N):
    if data[i] != None:
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if data[y] == None:
                data[y] = data[x] + dis[x][y]
                stack.append(y)
            else:
                if data[y] - data[x] != dis[x][y]:
                    print("No")
                    sys.exit()
    
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

graph = [[] for i in range(N)]
dis = [[None]*N for i in range(N)]

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

data = [None]*N
det = 0

for i in range(N):
    if data[i] != None:
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if data[y] == None:
                data[y] = data[x] + dis[x][y]
                stack.append(y)
            else:
                if data[y] - data[x] != dis[x][y]:
                    det = -1
                    break
    if det == -1:
        break

if det == 0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

graph = [[] for i in range(N)]
dis = [["n/a"]*N for i in range(N)]

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

data = ["n/a"]*N
det = 0

for i in range(N):
    if data[i] != "n/a":
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if data[y] == "n/a":
                data[y] = data[x] + dis[x][y]
                stack.append(y)
            else:
                if data[y] - data[x] != dis[x][y]:
                    det = -1
                    break
    if det == -1:
        break

if det == 0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
inf = 10 ** 10

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

graph = [[] for i in range(N)]
dis = [[inf]*N for i in range(N)]

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

data = [inf]*N
det = 0

for i in range(N):
    if data[i] != inf:
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if data[y] == inf:
                data[y] = data[x] + dis[x][y]
                stack.append(y)
            else:
                if data[y] - data[x] != dis[x][y]:
                    det = -1
                    break
    if det == -1:
        break

if det == 0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
inf = 10 ** 10

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

graph = [[] for i in range(N)]
dis = [[inf]*N for i in range(N)]

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

data = [inf]*N
det = 0

for i in range(N):
    if data[i] != inf:
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if data[y] == inf:
                data[y] = data[x] + dis[x][y]
                stack.append(y)
            else:
                if data[y] - data[x] != dis[x][y]:
                    det = -1
                    break
    if det == -1:
        break

if det == 0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

graph = [[] for i in range(N)]
dis = [["n/a"]*N for i in range(N)]

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

data = ["n/a"]*N
det = 0

for i in range(N):
    if data[i] != "n/a":
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if data[y] == "n/a":
                data[y] = data[x] + dis[x][y]
                stack.append(y)
            else:
                if data[y] - data[x] != dis[x][y]:
                    det = -1
                    break
    if det == -1:
        break

if det == 0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""

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

data=[[] for i in range(N+1)]
for m,(l,r,d) in enumerate(LRD):
    data[l].append([r,d,m])
    data[r].append([l,-d,m])
data2=[set([m[1] for m in data[i]]) for i in range(N+1)]
Mlst=set([i for i in range(M)])

visited=set()
X=[0 for i in range(N+1)]
while Mlst:
    stack=[LRD[Mlst.pop()][0]]
    while stack:
        l=stack.pop()
        visited.add(l)
        for r,d,m in data[l]:
            if not r in visited:
                visited.add(r)
                X[r]=X[l]+d
                stack.append(r)
                if m in Mlst:
                    Mlst.remove(m)
            else:
                if X[r]!=X[l]+d:
                    print("No")
                    exit()

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import queue
N,M=map(int,input().split())
s=[[]for i in range(N)]
used=set()
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))
    used.add(L-1)
    used.add(R-1)

q=queue.Queue()
dist=[-1]*N

while used!=set():
    a=used.pop()
    q.put(a)
    dist[a]=0
    while not q.empty():
        From=q.get()
        if From in used:
            used.remove(From)
        for l in s[From]:
            To,w=l
            if dist[To]==-1:
                dist[To]=dist[From]+w
                q.put(To)
            else:
                if dist[To]!=dist[From]+w:
                    print("No")
                    exit()
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import queue
N,M=map(int,input().split())
s=[[]for i in range(N)]
used=set()
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))
    used.add(L-1)
    used.add(R-1)

q=queue.Queue()
dist=[-1]*N
dist[0]=0

while used!=set():
    q.put(used.pop())
    while not q.empty():
        From=q.get()
        if From in used:
            used.remove(From)
        for l in s[From]:
            To,w=l
            if dist[To]==-1:
                dist[To]=dist[From]+w
                q.put(To)
            else:
                if dist[To]!=dist[From]+w:
                    print("No")
                    exit()
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
s=[[]for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))
sys.setrecursionlimit(200000)
l=[None]*N
a=1
def hu(n,x):
    global a
    for i in s[n]:
        if l[i[0]]==None:
            l[i[0]]=x+i[1]
            hu(i[0],x+i[1])
        else:
            if x+i[1]!=l[i[0]]:
                a=0
for i in range(N):
    if l[i]==None:
        l[i]=0
        hu(i,0)
print("Yes" if a else "No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
G=[[] for i in range(n)]

for i 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):
    dist=[None]*n
    q=deque()
    if dist[i]==None:
        dist[i]=0
    q.append(i)
    while q:
        cur=q.popleft()
        for nx,d in G[cur]:
            if dist[nx]==None:
                dist[nx]=dist[cur]+d
                q.append(nx)
            elif dist[nx]!=dist[cur]+d:
                print('No')
                exit()
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
People = {x+1:[] for x in range(10**6+1)}

for _ in range(m):
    l, r, d = map(int, input().split())
    People[l].append([r, d])
    People[r].append([l, -d])

INF = 10**10
Visited = [INF for i in range(10**6+1)]

def bfs(v):
    dq = deque()
    dq.append(v)
    Visited[v] = 0
    check = True
    while dq:
        now = dq.popleft()
        Related = People[now]
        for related in Related:
            if Visited[related[0]] == INF:
                dq.append(related[0])
                Visited[related[0]] = Visited[now] + related[1]
            elif Visited[related[0]] != Visited[now] + related[1]:
                check = False
    return check

ans = 'Yes'
for i in range(1,10**6+1):
    if Visited[i] == INF:
        if bfs(i) == False:
            ans = 'No'

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

visited = [False] * N
for i in range(N):
    if not visited[i]:
        dist = [float('inf')] * N
        dist[i] = 0
        stack = [i]
        while stack:
            v = stack.pop()
            visited[v] = True
            for u, d in G[v]:
                if dist[u] == float('inf'):
                    dist[u] = dist[v] + d
                elif dist[u] != dist[v] + d:
                    print('No')
                    exit()
                if not visited[u]:
                    stack.append(u)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


def dfs(v):
    visited[v] = True
    for u, d in G[v]:
        if dist[u] == float('inf'):
            dist[u] = dist[v] + d
        elif dist[u] != dist[v] + d:
            print('No')
            exit()
        if not visited[u]:
            dfs(u)


dist = []
visited = [False] * N
for v in range(N):
    if not visited[v]:
        dist = [float('inf')] * N
        dist[v] = 0
        dfs(v)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


def dfs(v):
    visited[v] = True
    for u, d in G[v]:
        if dist[u] == float('inf'):
            dist[u] = dist[v] + d
        if dist[u] != dist[v] + d:
            print('No')
            exit()
        dfs(u)


dist = []
visited = [False] * N
for v in range(N):
    if not has_parent[v]:
        dist = [float('inf')] * N
        dist[v] = 0
        dfs(v)
if all(visited):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


def dfs(v):
    visited[v] = True
    for u, d in G[v]:
        if dist[u] == float('inf'):
            dist[u] = dist[v] + d
        elif dist[u] != dist[v] + d:
            print('No')
            exit()
        if not visited[u]:
            dfs(u)


dist = []
visited = [False] * N
for v in range(N):
    if not visited[v]:
        dist = [float('inf')] * N
        dist[v] = 0
        dfs(v)
print('Yes')

Submission status: Time Limit Exceeded

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


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


N, M = map(int, input().split())
G = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    G[i][i] = 0
LRD = [None] * M
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L][R] = D
    LRD[i] = (L, R, D)
floyd_warshall(G)
for L, R, D in LRD:
    if G[L][R] != D or G[R][L] != float('inf'):
        print('No')
        exit()
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
connection=[[] for i in range(n)]
for i in range(m):
  connection[l[i][0]-1].append((l[i][1]-1,l[i][2]))
  connection[l[i][1]-1].append((l[i][0]-1,-l[i][2]))

distance=[-999999999999]*n

def bfs(v):
  distance[v]=0
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j][0]]==-1:
            distance[connection[next[i]][j][0]]=distance[next[i]]+connection[next[i]][j][1]
            next2.add(connection[next[i]][j][0])
    next=list(next2)
    next2=set()

for i in range(n):
  if distance[i]==-999999999999:
    bfs(i)

for i in range(m):
  if distance[l[i][1]-1]-distance[l[i][0]-1]!=l[i][2]:
    print('No')
    sys.exit()
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
connection=[[] for i in range(n)]
for i in range(m):
  connection[l[i][0]-1].append((l[i][1]-1,l[i][2]))
  connection[l[i][1]-1].append((l[i][0]-1,-l[i][2]))

distance=[-999999999999]*n

def bfs(v):
  distance[v]=0
  next=[v]
  next2=set()
  visited=[-1]*n
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j][0]]==-1:
            distance[connection[next[i]][j][0]]=distance[next[i]]+connection[next[i]][j][1]
            next2.add(connection[next[i]][j][0])
    next=list(next2)
    next2=set()
  return distance

for i in range(n):
  if distance[i]==-999999999999:
    distance=bfs(i)

for i in range(m):
  if distance[l[i][1]-1]-distance[l[i][0]-1]!=l[i][2]:
    print('No')
    sys.exit()
print('Yes')

Submission status: Time Limit Exceeded

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

n,m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append([tmp[1]-1,tmp[2]])
    link[tmp[1]-1].append([tmp[0]-1,-tmp[2]])
from collections import deque
vis=[False]*n
dist=[0]*n
for i in range(n):
    if vis[i]:
        continue
    vis[i] = True
    Q = deque()
    Q.append([i,0])
    while Q:
        now,cnt = Q.popleft()
        vis[now]=True
        for nxt,nxt_dist in link[now]:
            if dist[nxt] != cnt+nxt_dist:# NG or 0
                if vis[nxt]:
                    print("No")
                    exit()
                dist[nxt] = cnt+nxt_dist
            if not vis[nxt]:
                Q.append([nxt,cnt+nxt_dist])
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append([tmp[1]-1,tmp[2]])
    link[tmp[1]-1].append([tmp[0]-1,-tmp[2]])
from collections import deque
vis=[False]*n
dist=[0]*n
for i in range(n):
    if vis[i]:
        continue
    vis[i] = True
    Q = deque()
    Q.append([i,0])
    while Q:
        now,cnt = Q.popleft()
        vis[now]=True
        for nxt,nxt_dist in link[now]:
            if dist[nxt] != cnt+nxt_dist:# NG or 0
                if vis[nxt]:
                    print("No")
                    exit()
                dist[nxt] = cnt+nxt_dist
            if not vis[nxt]:
                Q.append([nxt,cnt+nxt_dist])
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import queue

n,m = map(int,input().split())

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

for i in range(m):
    g1,g2,L =  map(int,input().split())
    dis[g1-1].append((g2-1,L))
    dis[g2-1].append((g1-1,-L))




geo = [0.5] * n

q = queue.Queue()


for i in range(n):
    if geo[i] == 0.5:
        q.put(i)
        while not q.empty():
            g1 = q.get()
            for g2,L in dis[g1]:
                if geo[g2] == 0.5:
                    geo[g2] = geo[g1] + L
                    q.put(g2)
                else:
                    if geo[g2] != geo[g1] + L:
                        print("No")
                        exit()
print("Yes")

Submission status: Time Limit Exceeded

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

INF = 10**18
N, M = map(int, input().split())
g = [[] for _ in range(N)]
lst = [INF] * N

def dfs(v):
    for n, d in g[v]:
        if lst[n] == INF:
            lst[n] = lst[v] + d
            if not dfs(n):
                return False
        else:
            if lst[n] != lst[v] + d:
                return False
    return True

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

for i in range(N):
    if lst[i] == INF:
        lst[i] = 0
        if not dfs(i):
            print('No')
            exit()

print('Yes')

Submission status: Time Limit Exceeded

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

def tree(s):
    flag=True
    INF=-10**9
    dis = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)
        while len(d):
            x = d.popleft()
            for i,j in vec[x]:
                if dis[i] == INF:
                    dis[i]=dis[x]+j
                    d.append(i)
                else:
                    if dis[i]==dis[x]+j:
                        continue
                    else:
                        print('No')
                        exit()
        return flag
    return bfs()


n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
vec= [[] for i in range(n)]

for i in range(m):
    vec[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    vec[a[i][1]-1].append((a[i][0]-1,-a[i][2]))

INF=float('inf')
visited=[INF]*n

for i in range(n):
    if visited[i]==INF:
        tree(i)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import collections
from collections import deque

def tree(s):
    flag=True
    INF=-10**9
    dis = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)
        while len(d):
            x = d.popleft()
            for i,j in vec[x]:
                if dis[i] == INF:
                    dis[i]=dis[x]+j
                    d.append(i)
                else:
                    if dis[i]==dis[x]+j:
                        continue
                    else:
                        print('No')
                        exit()
        return flag
    return bfs()


n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
vec= [[] for i in range(n)]

for i in range(m):
    vec[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    vec[a[i][1]-1].append((a[i][0]-1,-a[i][2]))

INF=float('inf')
visited=[INF]*n

for i in range(n):
    if visited[i]==INF:
        if tree(i):
            continue
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
N, M = map(int, input().split())
graph = [[] * N for _ in range(N)]
for _ in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    graph[L].append((R, D))
    graph[R].append((L, -D))


def dfs(node, dist):
    global visited
    global dists
    dists[node] = dist
    for next, d in graph[node]:
        if next in visited:
            if d + dist != dists[next]:
                print('No')
                sys.exit()
        else:
            visited.add(next)
            dfs(next, dist + d)


visited = set()
dists = [0] * N
for i in range(N):
    if i in visited:
        continue
    visited.add(i)
    dfs(i, 0)

print('Yes')

Submission status: Time Limit Exceeded

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 _ in range(2):
    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()