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:
vs = set()
def dfs_w(d, stack):
    S, F, depth, depthh = [], [None]+[0]*N, [-1] + [0]*N, [0] + [0]*N
    path = [0]
    pvs = set()
    if stack[0] in vs:
        return True
    while stack:
        v, dpd = stack.pop()
        if v > 0:
            parent = path[-1]
            path.append(v)
            vs.add(v)
            pvs.add(v)

            F[v] = len(S)
            depth[v], depthh[v] = depth[parent] + 1, depthh[parent] + dpd

            S.append(v)
            for u, dpd in d[v]:
                if u in pvs:
                    if depthh[u] != depthh[v] + dpd:
                        return False
                if u in vs:
                    continue
                stack += [(-v, dpd), (u, dpd)]
        else:
            path.pop()
            S.append(v)

    return True
#    return S, F, depth, depthh

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

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

def main():
    N, M = map(int, input().split())
    d = [[-1] * N for _ in range(N)]
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        d[L][R] = D
        d[R][L] = D
        for i in range(N):
            if d[L][i] != -1 and d[i][R] != -1:
                if d[L][R] != d[L][i] + d[i][R]:
                    print('No')
                    exit()
    
    print('Yes')

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

L=[[]for i in range(N+1)]
D=dict()
for i in range(M):
    l,r,d=map(int,input().split())
    L[l].append([r,d])
    L[r].append([l,-d])
    D[i]=(l,r,d)
    
C=["N" for i in range(N+1)]

def dfs(x):
    for i,j in L[x]:
        if C[i]=="N":
            C[i]=C[x]+j
            dfs(i)

for i in range(1,N+1):
    if C[i]=="N":
        C[i]=0
        dfs(i)
#print(C)
#print(D)
for i in range(M):
    l,r,d=D[i]
    if C[r]-C[l]!=d:
        print("No")
        exit()
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def calc(A, B, C, now_t):
    ans = A * now_t + B * math.sin(C * now_t * math.pi)
    return ans


def main():
    num, hint_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(hint_num)]

    graph_data = defaultdict(set)
    dist_data = defaultdict(int)
    dist_ind = defaultdict(int)
    for i in range(hint_num):
        l, r , d = data[i]
        graph_data[l].add(r)
        graph_data[r].add(l)
        dist_data[(l, r)] = d
        dist_data[(r, l)] = -1 * d
        dist_ind[(l, r)] = i
        dist_ind[(r, l)] = i

    position = ['x' for i in range(num + 1)]
    dist_visit = [0 for i in range(hint_num)]
    check_point = [0 for i in range(num + 1)]

    flg = 1
    for i in range(hint_num):
        if dist_visit[i]:
            continue
        # dist_visit[i] = 1

        l, r, d = data[i]
        now_set = set()
        next_set = set()
        now_set.add(l)
        now_set.add(r)

        while len(now_set) > 0:
            for now_ele in now_set:
                if position[now_ele] == 'x':
                    position[now_ele] = 0

                for next_ele in graph_data[now_ele]:
                    if check_point[next_ele]:
                        continue
                    length = dist_data[(now_ele, next_ele)]
                    len_ind = dist_ind[(now_ele, next_ele)]
                    if dist_visit[len_ind]:
                        continue
                    dist_visit[len_ind] = 1
                    if position[next_ele] == 'x':
                        position[next_ele] = position[now_ele] + length
                        next_set.add(next_ele)
                    else:
                        if position[next_ele] != position[now_ele] + length:
                            flg = 0
                            break
                check_point[now_ele] = 1
            now_set = next_set
            next_set = set()

    # print(position)

    max_data = -10 ** 10
    min_data = 10 ** 10
    for i in range(1, num + 1):
        if position[i] == 'x':
            continue
        max_data = max(max_data, position[i])
        min_data = min(min_data, position[i])

    if max_data - min_data > 10 ** 9:
        flg = 0

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





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
sys.setrecursionlimit(10**6)
N,M=map(int,input().split())

D=[]
P=[[i,0]for i in range(N+1)]
C=[1 for i in range(N+1)]
A=[0]

for i in range(M):
    l,r,d=map(int,input().split())
    P[r]=[l,d]
    D.append([l,r,d])
#print(P)
def find(a,b):
    if c[a]==0:
        return a,b
    elif a==P[a][0]:
        return a,b
    else:
        c[a]=0
        return find(P[a][0],b+P[a][1])
for i in range(1,N+1):
    c=copy.deepcopy(C)
    A.append(find(i,0))
#print(A)
for i in range(M):
    if A[D[i][1]][1]-A[D[i][0]][1]!=D[i][2]:
        print("No")
        exit()
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict, deque

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    visited = 0
    pos = [None] * N
    adj = [set() for _ in range(N)]

    for l, r, d in zip(L, R, D):
        adj[l].add((r, d))
        adj[r].add((l, -d))
    
    for i in range(N):
        if (visited >> i) % 2 == 1:
            continue
        pos[i] = 0
        Q = deque([i], M)
        while len(Q) > 0:
            u = Q.popleft()
            visited |= 1 << u
            for v, d in adj[u]:
                if pos[v] is None:
                    pos[v] = pos[u] + d
                elif pos[v] != pos[u] + d:
                    print(NO)
                    return

                if (visited >> v) % 2 == 1:
                    continue
                Q.append(v)
    print(YES)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens)) - 1
        R[i] = int(next(tokens)) - 1
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict, deque

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    visited = [False] * N
    pos = [None] * N
    adj = defaultdict(set)

    for l, r, d in zip(L, R, D):
        adj[l].add((r, d))
        adj[r].add((l, -d))
    
    for i, vis in enumerate(visited):
        if vis:
            continue
        pos[i] = 0
        Q = deque([i], M)
        while len(Q) > 0:
            u = Q.popleft()
            visited[u] = True
            for v, d in adj[u]:
                if pos[v] is None:
                    pos[v] = pos[u] + d
                elif pos[v] != pos[u] + d:
                    print(NO)
                    return

                if visited[v]:
                    continue
                Q.append(v)
    print(YES)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    D = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        L[i] = int(next(tokens)) - 1
        R[i] = int(next(tokens)) - 1
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

A = [[] for i in range(N)]

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

dist = [False for i in range(N)]

ans = "Yes"

flg = 0

for i in range(N) :
    if flg :
        break
    
    if dist[i] :
        continue
    
    dist[i] = 0
    
    q = [i]
    
    while q :
        now = q.pop()
        for to,d in A[now] :
            if not dist[to] :
                dist[to] = dist[now] + d
                q.append(to)
            
            elif dist[to] == dist[now] + d :
                continue
            
            else :
                ans = "No"
                flg = 1
                q = []
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

A = [[] for i in range(N)]

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

dist = [False for i in range(N)]

ans = "Yes"

flg = 0

for i in range(N) :
    if flg :
        break
    
    if dist[i] :
        continue
    
    dist[i] = 0
    
    q = deque([i])
    
    while q :
        now = q.pop()
        for to,d in A[now] :
            if not dist[to] :
                dist[to] = dist[now] + d
                q.append(to)
            
            elif dist[to] == dist[now] + d :
                continue
            
            else :
                ans = "No"
                flg = 1
                q = deque()
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

A = [[] for i in range(N)]

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

dist = [False for i in range(N)]

ans = "Yes"

flg1 = 0
flg2 = 0

for i in range(N) :
    if flg1 :
        break
    
    if dist[i] :
        continue
    
    dist[i] = 0
    
    q = deque([i])
    
    while q :
        if flg2 :
            break
        
        now = q.pop()
        for to,d in A[now] :
            if not dist[to] :
                dist[to] = dist[now] + d
                q.append(to)
            
            elif dist[to] == dist[now] + d :
                continue
            
            else :
                ans = "No"
                flg1 = 1
                flg2 = 1
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, sys.stdin.readline().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, sys.stdin.readline().split())
    l, r = l - 1, r - 1
    G[l].append((r, d))
    G[r].append((l, -d))

R = [None] * N


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


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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, sys.stdin.readline().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, sys.stdin.readline().split())
    l, r = l - 1, r - 1
    G[l].append((r, d))
    G[r].append((l, -d))

R = [None] * N


def dfs(u):
    global R, G
    for w, d in G[u]:
        if not R[w]:
            R[w] = R[u] + d
            if not dfs(w):
                return False
        else:
            if R[w] != R[u] + d:
                return False
    return True


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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, sys.stdin.readline().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, sys.stdin.readline().split())
    l, r = l - 1, r - 1
    G[l].append((r, d))
    G[r].append((l, -d))

R = [None] * N


def dfs(u):
    global R, G
    for w, d in G[u]:
        if not R[w]:
            R[w] = R[u] + d
            if not dfs(w):
                return False
        else:
            if R[w] != R[u] + d:
                return False
    return True


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

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, input().split())
G = [[] for i 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))

R = [None] * N


def dfs(u):
    global R, G
    for w, d in G[u]:
        if not R[w]:
            R[w] = R[u] + d
            if not dfs(w):
                return False
        else:
            if R[w] != R[u] + d:
                return False
    return True


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

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, input().split())
G = [[] for i 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))

R = [None] * N


def dfs(u):
    for w, d in G[u]:
        if not R[w]:
            R[w] = R[u] + d
            if not dfs(w):
                return False
        else:
            if R[w] != R[u] + d:
                return False
    return True


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

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n,m = map(int,input().split())
uf = [-1]*n
def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx==ry: return False
    if rx > ry: rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

edge = [[-1]*n for i in range(n)]
edge = defaultdict(list)
for i in range(m):
    l,r,d = map(int, input().split())
    edge[l-1].append((r-1,d))
    edge[r-1].append((l-1,-d))
    unite(l-1, r-1)

dist = [0]*n
visited = [False]*n

from collections import deque

for i in range(n):
    if uf[i] >= 0:
        continue
    q = deque()
    q.append((i,0))
    while q:
        to, d = q.popleft()
        if visited[to]:
            if dist[to] != d:
                print("No")
                exit()
        else:
            visited[to] = True
            dist[to] = d
            for ind, j in edge[to]:
                q.append((ind,d+j))

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n,m = map(int,input().split())
uf = [-1]*n
def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx==ry: return False
    if rx > ry: rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

edge = [[-1]*n for i in range(n)]
edge = defaultdict(list)
for i in range(m):
    l,r,d = map(int, input().split())
    edge[l-1].append((r-1,d))
    edge[r-1].append((l-1,-d))
    unite(l-1, r-1)

dist = [0]*n
visited = [False]*n
ans = True

def bfs(p, d=0):
    global ans
    if not ans:
        return
    if not visited[p]:
        visited[p] = True
        dist[p] = d
        for ind, j in edge[p]:
            bfs(ind, d+j)
    else:
        if dist[p] != d:
            ans = False

for i in range(n):
    if uf[i] >= 0:
        continue
    bfs(i, 0)
    if not ans:
        break

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
uf = [-1]*n
def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx==ry: return False
    if rx > ry: rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

edge = [[-1]*n for i in range(n)]
for i in range(m):
    l,r,d = map(int, input().split())
    edge[l-1][r-1] = d
    edge[r-1][l-1] = -d
    unite(l-1, r-1)

dist = [0]*n
visited = [False]*n
ans = True

def bfs(p, d=0):
    global ans
    if not visited[p]:
        visited[p] = True
        dist[p] = d
        for ind, j in enumerate(edge[p]):
            if j>= 0:
                bfs(ind, d+j)
    else:
        if dist[p] != d:
            ans = False

for i in range(n):
    if uf[i] >= 0:
        continue
    bfs(i, 0)
    if not ans:
        break

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n,m = map(int,input().split())
uf = [-1]*n
def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx==ry: return False
    if rx > ry: rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

edge = [[-1]*n for i in range(n)]
for i in range(m):
    l,r,d = map(int, input().split())
    edge[l-1][r-1] = d
    edge[r-1][l-1] = -d
    unite(l-1, r-1)

dist = [0]*n
visited = [False]*n
ans = True

def bfs(p, d=0):
    global ans
    if not visited[p]:
        visited[p] = True
        dist[p] = d
        for ind, j in enumerate(edge[p]):
            if j>= 0:
                bfs(ind, d+j)
    else:
        if dist[p] != d:
            ans = False

for i in range(n):
    if uf[i] >= 0:
        continue
    bfs(i, 0)
    if not ans:
        break

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M = map(int, input().split())
LRD = [ [int(j) for j in input().split()] for _ in range(M)]

data = [-1] * (N+1)
rank = [0]  * (N+1)
diff_weight = [0] * (N+1)

def root(x):
    if data[x] == x:
        return x
    else:
        r = root(x)
        diff_weight[x] += diff_weight[ data[x] ]
        data[x] = r
        return r

def weight(x):
    _ = root(x)
    return diff_weight[x]


def diff(x,y):
    return weight(y) - weight(x)

def merge(x,y,w):
    w  += weight(x); w -= weight(y)
    x = root(x)
    y = root(y)
    if x == y: return False
    if rank[x] < rank[y]: x,y = y,x; w = -w
    if rank[x] == rank[y]: rank[x] += 1
    data[y] = x
    diff_weight[y] = w
    return True

def issame(x,y):
    return root(x) == root(y)

for i in range(M):
    L,R,D = LRD[i]
    if not issame(L,R):
        merge(L,R,D)
    else:
        if weight(L,R) != D:
            print("No")
            exit(0)
            
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
LRD = [ [int(j) for j in input().split()] for _ in range(M)]
MAP = [ [] for _ in range(N+1)]
CR  = [ [0] * (N+1) for _ in range(N+1)]

def canDFS(node, par, target):
    if len(list(filter(lambda x: x!=par, MAP[node]))) == 0:
        return float("inf")
    if target in MAP[node]:
        return CR[node][target]

    ans = float("inf")
    for ch in MAP[node]:
        if ch == par: continue
        tmp = CR[node][ch]
        tmp += canDFS(ch, node,target)
        if tmp < ans:
            ans = tmp
    return ans
        


for i in range(M):
    L,R,D = LRD[i]
    
    LtoR = canDFS(L, -1, R)
    # print("LRD:", L,R,D, LtoR)

    if LtoR == D:
        continue
    elif LtoR == float("inf"):
        MAP[L].append(R)
        MAP[R].append(L)
        
        CR[L][R] = D
        CR[R][L] = -D
        # print("\tappend")
    else:
        print("No")
        exit(0)
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
edge = [[None]*(N+1) for _ in range(N+1)]
for _ in range(M):
    l,r,d = map(int,input().split())
    edge[l][r] = d
    edge[r][l] = -d
G = [None]*(N+1)
ok = True
stack = []
for x in range(1,N+1):
    if G[x] is not None: continue
    G[x] = 0
    stack = [x]
    while stack:
        v = stack.pop()
        for to in range(1,N+1):
            if edge[v][to] is None:
                continue
            d = edge[v][to]
            if G[to] is None:
                G[to] = G[v] + d
                stack.append(to)
            else:
                if G[to] != G[v] + d:
                    ok = False
                    break
    if ok == False:
        break
print('Yes' if ok else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

n, m = map(int, input().split())
ed = [[] for _ in range(n)]
v = [None] * n
for _ in range(m):
	l, r, d = map(int, input().split())
	ed[l-1].append([r-1, d])
	ed[r-1].append([l-1, -d])

def bfs(start):
	global ed, v
	visited = [False] * n
	s = deque([start])
	v[start] = 0
	while s:
		label = s.pop()
		if visited[label] == False:
			visited[label] = True
			for e in ed[label]:
				if v[e[0]] is None:
					v[e[0]] = v[label] + e[1]
					s.appendleft(e[0])
				else:
					if v[e[0]] != v[label] + e[1]:
						print("No")
						sys.exit()
	return

for i in range(n):
	if v[i] is None:
		bfs(i)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys

n, m = map(int, input().split())
ed = [[] for _ in range(n)]
v = [None] * n
for _ in range(m):
	l, r, d = map(int, input().split())
	ed[l-1].append([r-1, d])
	ed[r-1].append([l-1, -d])

def dfs(start):
	global ed, v
	visited = [False] * n
	s = [start]
	v[start] = 0
	while s:
		label = s.pop()
		if visited[label] == False:
			#print(label)
			visited[label] = True
			for e in ed[label]:
				if v[e[0]] is None:
					v[e[0]] = v[label] + e[1]
					s.append(e[0])
				else:
					if v[e[0]] != v[label] + e[1]:
						print("No")
						sys.exit()
	return

for i in range(n):
	if v[i] is None:
		#print(i)
		dfs(i)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
Inf = 10000000000
Edge = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, input().split())
    Edge[l-1].append((r-1, d))
    Edge[r-1].append((l-1, -d))

Node = [Inf for i in range(N)]
Possible = True
for i in range(N):
    if not Possible:
        break
    elif Node[i] == Inf:
        Node[i] = 0
        Q = [i]
        while Q:
            now = Q.pop(0)
            for e in Edge[now]:
                if Node[e[0]] == Inf:
                    Node[e[0]] = Node[now] + e[1]
                    Q.append(e[0])
                elif Node[now] + e[1] != Node[e[0]]:
                    Possible = False
                    break
print("Yes" if Possible else "No")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
Edge = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, input().split())
    Edge[l-1].append((r-1, d))
    Edge[r-1].append((l-1, -d))
Left = [int(i) for i in range(N)]
Visit = [False for i in range(N)]
Node = [0 for i in range(N)]
Possible = True

while Left and Possible:
    start = Left.pop(0)
    Visit[start] = True
    Q = [start]
    while Q:
        now = Q.pop(0)
        for e in Edge[now]:
            if Visit[e[0]] == False:
                Visit[e[0]] = True
                Left.remove(e[0])
                Node[e[0]] = Node[now] + e[1]
                Q.append(e[0])
            elif e[0] != now:
                dest = Node[now] + e[1]
                if dest != Node[e[0]]:
                    Possible = False
                    break
print("Yes" if Possible else "No")

Submission status: Time Limit Exceeded

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

N,M = map(int,input().split())
Graph =[[] for i in range(N)]
for i in range(M):
    L,R,D = map(int,input().split())
    Graph[L-1].append((R-1,D))
    Graph[R-1].append((L-1 ,-D))
visit=[False]*N
for i in range(N):
    if visit[i]==False:
        visit[i]=0
        A = deque()
        A.append(i)
        while A:
            x = A.pop()
            for y,d in Graph[x]:
                if (visit[y] != False) and (visit[y]!=d+visit[x]):
                    print('No')
                    sys.exit()
                elif (visit[y] == False):
                    A.append(y)
                    visit[y]=d+visit[x] 
    
print('Yes')

Submission status: Time Limit Exceeded

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

checked = [0] * N
for i in range(N):
    if checked[i]: continue
    dist = [None] * N
    dist[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        checked[v] = 1
        for to,d in es[v]:
            if dist[to] is None:
                dist[to] = dist[v] + d
                if not checked[to]:
                    stack.append(to)
            else:
                if dist[to] != dist[v] + d:
                    print('No')
                    exit()
print('Yes')

Submission status: Time Limit Exceeded

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

checked = [0] * N
for i in range(N):
    if checked[i]: continue
    dist = [None] * N
    dist[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        checked[v] = 1
        for to,d in es[v]:
            if dist[to] is None:
                dist[to] = dist[v] + d
                if not checked[to]:
                    stack.append(to)
            else:
                if dist[to] != dist[v] + d:
                    print('No')
                    exit()
print('Yes')

Submission status: Time Limit Exceeded

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

checked = [0] * N
for i in range(N):
    if checked[i]: continue
    dist = [-1] * N
    dist[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        checked[v] = 1
        for to,d in es[v]:
            if dist[to] < 0:
                dist[to] = dist[v] + d
                stack.append(to)
            else:
                if dist[to] != dist[v] + d:
                    print('No')
                    exit()
print('Yes')

Submission status: Time Limit Exceeded

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

def consistent(LRD):
    for i, (l1, r1, d1) in enumerate(LRD):
        candl = []
        candr = []
        for j, (l2, r2, d2) in enumerate(LRD):
            if i < j:
                continue
            if l2 == l1:
                candl.append((r2, d2))
            if r2 == r2:
                candr.append((l2, d2))
        for tl in candl:
            for tr in candr:
                if tl[0] == tr[0] and tl[1] + tr[1] != d1:
                    return False
    return True

if consistent(LRD):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, raw_input().split())
a = []
for i in range(M):
	a.append(map(int, raw_input().split()))
x = [0 for i in range(N)]
y = [0 for i in range(N)]
layer = 1
answer = 'Yes'
for i in range(M):
	L = a[i][0]
	R = a[i][1]
	D = a[i][2]
	if y[L-1] == 0 and y[R-1] == 0:
		x[R-1] = x[L-1] + D
		y[L-1] = layer
		y[R-1] = layer
	elif y[L-1] == 0 and y[R-1] > 0:
		x[L-1] = x[R-1] - D
		y[L-1] = y[R-1]
	elif y[L-1] > 0 and y[R-1] == 0:
		x[R-1] = x[L-1] + D
		y[R-1] = y[L-1]
	elif y[L-1] > 0 and y[R-1] > 0:
		if y[L-1] == y[R-1]:
			if x[R-1] - x[L-1] != D:
				answer = 'No'
				break
		else:
			dx = x[L-1] + D - x[R-1]
			h = y[R-1]
			for j in range(N):
				if y[j] == h:
					x[j] = x[j] + dx
					y[j] = y[L-1]
	layer = layer + 1
print answer