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:
n,m = map(int,input().split())
branch = dict()
for i in range(1,n+1):
    branch[i] = []
for i in range(m):
    l,r,d = map(int,input().split())
    branch[l].append([r,d])
    branch[r].append([l,-d])

arrival = [0 for i in range(n+1)]
arrival[0] = 1
comp = [1 for i in range(n+1)]
place = [0 for i in range(n+1)]
q = [1]
check = True
p = 1

while arrival != comp and check:
    if len(q) != 0:
        arrival[q[0]] = 1
        next = branch[q[0]]
        for i in range(len(next)):
            if arrival[next[i][0]] == 0:
                q.append(next[i][0])
                place[next[i][0]] = place[q[0]] + next[i][1]
            else:
                if place[next[i][0]] != place[q[0]] + next[i][1]:
                    check = False
        q.pop(0)
    else:
        while arrival[p] == 1:
            p += 1
        q.append(p)

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

Submission status: Time Limit Exceeded

Solution code:

class MakeGraph:
    
    # 隣接行列もしくは隣接リストの初期化
    # node_num：ノード数
    # isMat：隣接行列(True) / 隣接リスト(False)
    def __init__(self, node_num:int, isMat:bool) -> None:
        self.n = node_num
        self.isMat = isMat

        # 隣接行列の初期化
        if self.isMat:
            INF = float("inf")
            self.graph = [[INF for _ in range(self.n)] for _ in range(self.n)]
    
        # 隣接リストの初期化
        else:
            self.graph = [[] for _ in range(self.n)]

    # エッジの追加
    # frm, to：起点ノード, 終点ノード
    # directed:有向(True) / 無向(False)
    def add_edge(self, frm:int, to:int, dist:int, directed=False) -> None:
        if self.isMat:
            if directed:
                self.graph[frm][to] = dist
            else:
                self.graph[frm][to] = dist
                self.graph[to][frm] = dist
        else:
            if directed:
                self.graph[frm].append((dist, to))
            else:
                self.graph[frm].append((dist, to))
                self.graph[to].append((dist, frm))
                
    # 完成したグラフを取り出す
    def get_graph(self) -> list:
        return self.graph


N,M = map(int, input().split())
LRD = []
for _ in range(M):
    LRD.append(tuple(map(int, input().split())))
    
graphMaker = MakeGraph(N,False)

for l,r,d in LRD:
    graphMaker.add_edge(l-1,r-1,d,True)
    graphMaker.add_edge(r-1,l-1,-d,True)
    
graph = graphMaker.get_graph()

INF = 10**10
dist = [-INF]*N

# 座標割り当て(dfs)
for i in range(N):
    stack = [i]
    while len(stack):
        v = stack.pop()

        for cost, nex_node in graph[v]:
            if dist[nex_node] != -INF:
                continue
            dist[nex_node] = dist[v] + cost
            stack.append(nex_node)
                
    else:
        continue

# 矛盾チェック
consistent = True
for l,r,d in LRD:
    if dist[r-1]-dist[l-1] != d:
        print("No")
        consistent = False
        break
    
if consistent:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, LRD):
    # print(LRD)
    g = [[] for _ in range(N)]
    ns = set([])
    for l ,r, d in LRD:
        g[l-1].append((r-1,d))
        g[r-1].append((l-1,-d))
        ns.add(l-1)
        ns.add(r-1)      
    
    G =  [None for _ in range(N)]

    if M == 0:
        return 'Yes'

    ns = {n:n for n in ns}
    while ns:
        q = [list(ns.keys())[0]]
        ns.pop(q[0])
        # print(q)
        G[q[0]] = 0
        while q:
            n = q.pop(0)
            for r, d in g[n]:
                if G[r] is None:
                    G[r] = G[n] + d
                    q.append(r)
                    if r in ns:
                        ns.pop(r)
                else:
                    if G[r] != G[n] + d:
                        return 'No'
                        # pass
    
    return 'Yes'
            



def main():
    N, M = read_int_n()
    LRD = [read_int_n() for _ in range(M)]

    # N = 100000
    # M = 200000
    # LRD = [[random.randint(1, N), random.randint(1, N), random.randint(1, 10000)] for _ in range(M) ]
    print(slv(N, M, LRD))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, LRD):
    # print(LRD)
    g = [[] for _ in range(N)]
    ns = set([])
    for l ,r, d in LRD:
        g[l-1].append((r-1,d))
        g[r-1].append((l-1,-d))
        ns.add(l-1)
        ns.add(r-1)      
    
    G =  [None for _ in range(N)]

    if M == 0:
        return 'Yes'

    ns = list(ns)
    while ns:
        q = [ns.pop(0)]
        # print(q)
        G[q[0]] = 0
        while q:
            n = q.pop(0)
            for r, d in g[n]:
                if G[r] is None:
                    G[r] = G[n] + d
                    q.append(r)
                    if r in ns:
                        ns.remove(r)
                else:
                    if G[r] != G[n] + d:
                        return 'No'
                        # pass
    
    return 'Yes'
            



def main():
    N, M = read_int_n()
    LRD = [read_int_n() for _ in range(M)]

    # N = 100000
    # M = 200000
    # LRD = [[random.randint(1, N), random.randint(1, N), random.randint(1, 10000)] for _ in range(M) ]
    print(slv(N, M, LRD))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, LRD):
    # print(LRD)
    g = [[] for _ in range(N)]
    ns = set([])
    for l ,r, d in LRD:
        g[l-1].append((r-1,d))
        g[r-1].append((l-1,-d))
        ns.add(l-1)
        ns.add(r-1)      
    
    G =  [None for _ in range(N)]

    if M == 0:
        return 'Yes'

    while ns:
        q = [list(ns)[0]]
        ns -= set([q[0]])
        # print(q)
        G[q[0]] = 0
        while q:
            n = q.pop(0)
            for r, d in g[n]:
                if G[r] is None:
                    G[r] = G[n] + d
                    q.append(r)
                    ns -= set([r])
                else:
                    if G[r] != G[n] + d:
                        return 'No'
                        # pass
    
    return 'Yes'
            



def main():
    N, M = read_int_n()
    LRD = [read_int_n() for _ in range(M)]

    # N = 100000
    # M = 200000
    # LRD = [[random.randint(1, N), random.randint(1, N), random.randint(1, 10000)] for _ in range(M) ]
    print(slv(N, M, LRD))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, LRD):
    # print(LRD)
    g = [[] for _ in range(N)]
    ns = set([])
    for l ,r, d in LRD:
        g[l-1].append((r-1,d))
        g[r-1].append((l-1,-d))
        ns.add(l)
        ns.add(r)      
    
    G =  [None for _ in range(N)]

    if M == 0:
        return 'Yes'

    while ns:
        q = [list(ns)[0]]
        G[q[0]] = 0
        while q:
            n = q.pop(0)
            for r, d in g[n]:
                if G[r] is None:
                    G[r] = G[n] + d
                    q.append(r)
                    ns -= set([r])
                else:
                    if G[r] != G[n] + d:
                        return 'No'
    
    return 'Yes'
            



def main():
    N, M = read_int_n()
    LRD = [read_int_n() for _ in range(M)]

    # N = 100000
    # M = 200000
    # LRD = [[random.randint(1, N), random.randint(1, N), random.randint(1, 10000)] for _ in range(M) ]
    print(slv(N, M, LRD))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, LRD):
    # print(LRD)
    g = [[None for _ in range(N)] for _ in range(N)]
    ns = set([])
    for l ,r, d in LRD:
        g[l-1][r-1] = d
        g[r-1][l-1] = -d
        ns.add(l)
        ns.add(r)      
    
    G =  [None for _ in range(N)]

    if M == 0:
        return 'Yes'

    q = [list(ns)[0]]
    G[q[0]] = 0
    while q:
        n = q.pop(0)
        for r, d in enumerate(g[n]):
            if d is None:
                continue
            if G[r] is None:
                G[r] = G[n] + d
                q.append(r)
            else:
                if G[r] != G[n] + d:
                    return 'No'
    
    return 'Yes'
            



def main():
    N, M = read_int_n()
    LRD = [read_int_n() for _ in range(M)]
    print(slv(N, M, LRD))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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



def func():
    visited = [False for i in range(n)]
    x = [None for i in range(n)]
    for i in range(n):
        if visited[i] == False:
            q = [i]
        while q:
            j = q.pop()
            visited[j] = True
            if x[j] == None:
                x[j] = 0
            for k, d in graph[j]:
                if visited[k] == False:
                    q.append(k)
                if x[k] == None:
                    x[k] = x[j] + d
                elif x[k] != x[j] + d:
                    return False
    return True

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
L = []
R = []
D = []
for i in range(M):
    l, r, d = map(int, input().split())
    L.append(l)
    R.append(r)
    D.append(d)

inf = float("inf")


class WDG():  # 重み付き有向グラフ(隣接リスト表現)
    class node():
        def __init__(self, index=0, weight=0, next=None):
            self.index = index
            self.weight = weight
            self.next = next

    def __init__(self, N, M, L, R, D):
        self.heads = []
        self.x = [None] * N
        self.N = N
        self.q = deque()
        for i in range(N):
            head = WDG.node()
            head.next = head
            head.index = i
            self.heads.append(head)
        for i in range(M):
            new1 = WDG.node(R[i] - 1, D[i], head)
            new2 = WDG.node(L[i] - 1, -D[i], head)
            self.insert(L[i] - 1, new1)
            self.insert(R[i] - 1, new2)

    def insert(self, start, new):
        new.next = self.heads[start].next
        self.heads[start].next = new

    def show_graph(self):
        for i in self.heads:
            node = i.next
            print("{}=>".format(i.index + 1), end="")
            while node != i:
                print("{}({})".format(node.index + 1, node.weight), end=" ")
                node = node.next
            print("")

    def _DFS(self, s_head):  # 始点sから到達できる連結成分を深さ優先探索
        node = s_head.next
        while node != s_head:
            new_x = self.x[s_head.index] + node.weight
            if self.x[node.index] is None:
                #print("node{}".format(node.index + 1))
                self.x[node.index] = new_x
                if not self._DFS(self.heads[node.index]):
                    return False
            elif self.x[node.index] != new_x:
                #print("node{}NG".format(node.index + 1))
                return False
            node = node.next
        return True

    def DFS(self):  # すべての点を訪れるまで深さ優先探索
        for i in range(self.N):
            node = self.heads[i]
            if self.x[node.index] is None:
                self.x[node.index] = 0
                if not self._DFS(self.heads[node.index]):
                    return "No"
        return "Yes"

    def _BFS(self, s_head):
        self.q.append(s_head)
        while len(self.q) != 0:
            p = self.q.popleft()
            node = p.next
            while node != p:
                if self.x[node.index] is None:
                    self.x[node.index] = self.x[p.index] + node.weight
                    self.q.append(self.heads[node.index])
                elif self.x[node.index] != self.x[p.index] + node.weight:
                    return False
                node = node.next
        return True

    def BFS(self):
        for i in range(self.N):
            node = self.heads[i]
            if self.x[i]is None:
                self.x[i] = 0
                if not self._BFS(node):
                    return "No"
        return "Yes"


G = WDG(N, M, L, R, D)
# G.show_graph()
# print(G.DFS())
print(G.BFS())

Submission status: Time Limit Exceeded

Solution code:
n,m = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(m)]
y,z,ans = [[] for i in range(n+1)],[None for i in range(n+1)],"Yes"
for i,j,k in x:
	y[i].append([j,k])
	y[j].append([i,-k])
for i in range(1,n+1):
	if z[i] == None:
		z[i],q = 0,[i]
		while q:
			p = q.pop()
			for j,k in y[p]:
				if z[j] == None: q,z[j] = q+[j],z[p]+k
for i in range(1,n+1):
	for j,k in y[i]:
		if z[i]+k != z[j]:
			ans = "No"
			break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(m)]
y,z,ans = [[] for i in range(n+1)],[None for i in range(n+1)],"Yes"
for i,j,k in x:
	y[i].append([j,k])
	y[j].append([i,-k])
for i in range(1,n+1):
	if z[i] == None:
		z[i],q = 0,[i]
		while q:
			p = q.pop()
			for j,k in y[p]:
				if z[j] == None: q,z[j] = q+[j],z[p]+k
for i in range(1,n+1):
	for j,k in y[i]:
		if z[i]+k != z[j]: ans = "No"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
LRD=[]
x={}
for i in range(M):
    l,r,d=map(int,input().split())
    LRD.append((l,r,d))
if LRD:
    x[LRD[0][0]]=0
flag=True
while LRD and flag:
    rmvlist=[]
    for i in range(len(LRD)):
        l,r,d=LRD[i]
        if l in x and r not in x:
            x[r] = x[l] +d
            rmvlist.append(i)
        elif r in x and l not in x:
            x[l] = x[r] -d
            rmvlist.append(i)
        elif l in x and r in x:
            if x[l] +d != x[r]:
                flag=False
                break
            else:
                rmvlist.append(i)
    if len(rmvlist)==0:
        x[LRD[0][0]]=0
    else:
        LRD=[LRD[i]for i in range(len(LRD)) if i not in rmvlist]

print("Yes No".split()[1-flag])

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n, m = map(int, raw_input().split())
    edge = {v:[] for v in range(1,n+1)}
    dist = {}
    for i in range(m):
        l, r, d = map(int, raw_input().split())
        edge[l].append(r)
        edge[r].append(l)
        dist[l,r] = d
        dist[r,l] = -d
    return "Yes" if ok(edge, dist, n) else "No"

def ok(edge, dist, n):
    used = [False] * (n+1)
    used[0] = True
    path = {}
    for s in range(1, n+1):
        if used[s]:
            continue
        que = [s]
        path[s, s] = 0
        used[s] = True
        while que:
            u = que.pop(0)
            for v in edge[u]:
                d = path[s,u] + dist[u,v]
                if not (s,v) in path:
                    path[s,v] = d
                    if not used[v]:
                        que.append(v)
                    used[v] = True
                elif d != path[s,v]:
                    return False
    return True

print solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n, m = map(int, raw_input().split())
    edge, dist = {}, {}
    for i in range(m):
        l, r, d = map(int, raw_input().split())
        if not l in edge:
            edge[l] = []
        edge[l].append(r)
        if not r in edge:
            edge[r] = []
        edge[r].append(l)
        dist[l,r] = d
        dist[r,l] = -d
    return "Yes" if ok(edge, dist, n) else "No"

def ok(edge, dist, n):
    used = [False] * (n+1)
    used[0] = True
    path = {}
    for s in range(1, n+1):
        if used[s]:
            continue
        que = [s]
        path[s, s] = 0
        used[s] = True
        while que != []:
            u = que.pop(0)
            if not u in edge:
                continue
            for v in edge[u]:
                d = path[s,u] + dist[u,v]
                if not (s,v) in path:
                    path[s,v] = d
                    used[v] = True
                    que.append(v)
                elif d != path[s,v]:
                    return False
    return True

print solve()

Submission status: Time Limit Exceeded

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

    n = [[-1 for _ in [0] * (N + 1)] for _ in [0] * (N + 1)]
    for l, r, d in LRD:
        n[l][r] = d
        n[r][l] = -d

    for l, r, d in LRD:
        dist = 0
        if abs(l - r) > 1:
            for i in range(min(l, r), max(l, r)):
                dist += n[i][i+1]
            if dist != n[l][r]:
                print('No')
                return
    print('Yes')

main()

Submission status: Time Limit Exceeded

Solution code:
def sub(a, b, n):
 r = a[:]
 for i in range(len(b)):
  r[i] -= b[i] * n
 return r

def mult(a, n):
 r = a[:]
 for i in range(len(a)):
  r[i] *= n
 return r

def pm(matr):
 return ""

def rref(matr):
 if len(matr) == 0 or len(matr[0]) == 0:
  return matr
 pivotCt = 0
 for d in range(max(len(matr), len(matr[0])-1)):
  #scan for first pivot
  pivot = None
  for i in range(len(matr)):
   allZeroes = True
   for j in range(d):
    if matr[i][j] != 0:
     allZeroes = False
     break
   if matr[i][d] != 0 and allZeroes:
    pivot = mult(matr[i], 1/matr[i][d])
    del matr[i]
    matr.insert(pivotCt, pivot)
    break
  if pivot != None:
   for i in range(len(matr)):
    if i != pivotCt and matr[i][d] != 0:
     matr[i] = sub(matr[i], pivot, matr[i][d])
   pivotCt += 1
 return matr

s = raw_input().split(" ")
vs = int(s[0])
es = int(s[1])

matr = []
for i in range(es):
 matr.append([0] * (vs + 1))
 q = raw_input().split(" ")
 x = int(q[0])
 y = int(q[1])
 z = int(q[2])
 matr[i][x] = 1
 matr[i][y] = -1
 matr[i][-1] = z

matr = rref(matr)
bad = False
for i in range(len(matr)):
 allZeroes = True
 for j in range(len(matr[0])-1):
  if matr[i][j] != 0:
   allZeroes = False
   break
 if allZeroes and matr[i][-1] != 0:
   bad = True
   break

if bad:
 print "No"
else:
 print "Yes"

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
peak = [[] for i in range(N)]
vector = []
queue = []
amount = ["n" for k in range(N)]
for i in range(M):
    temp = [int(i) for i in input().split()]
    peak[temp[0]-1].append([temp[1],temp[2]*(-1)])
    peak[temp[1]-1].append([temp[0],temp[2]])
    vector.append(temp)
 
 
f = []
 
def check(a,c):
    if amount[a-1] == "n":
        amount[a-1] = c
        queue.append(a)
        return
    else:
        if c == amount[a-1]:
            return
        else:
            f.append(0)
            return
for i in range(N):
    if f:
        break
    if amount[i] == "n":
        amount[i] = 0
        queue.append(i+1)
        while queue:
            if f:
                break
            a = queue.pop(0)
            for j in peak[a-1]:
                x,y = j[0],j[1]
                c = amount[a-1] + y
                check(x,c)
print("No" if f else "Yes")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
peak = [[] for i in range(N)]
vector = []
used = []
queue = []
amount = ["n" for k in range(N)]
for i in range(M):
    temp = [int(i) for i in input().split()]
    peak[temp[0]-1].append([temp[1],temp[2]*(-1)])
    peak[temp[1]-1].append([temp[0],temp[2]])
    vector.append(temp)


f = []

def check(a,c):
    if amount[a-1] == "n":
        amount[a-1] = c
        queue.append(a)
        return
    else:
        if c == amount[a-1]:
            return
        else:
            f.append(0)


for i in range(N):
    if f:
        break
    if amount[i] == "n":
        amount[i] = 0
        queue.append(i+1)
        while queue:
            if f:
                break
            a = queue.pop(0)
            for j in peak[a-1]:
                x,y = j[0],j[1]
                c = amount[a-1] + y
                check(x,c)
print("No" if f else "Yes")

Submission status: Time Limit Exceeded

Solution code:
data1 = input("")
n = int(data1.split(" ")[0])
m = int(data1.split(" ")[1])
data2 = [0]*m
l = [0]*m
r = [0]*m
d = [0]*m
flag = 0

for i in range(m):
    data2[i] = input("")
    l[i] = int(data2[i].split(" ")[0])
    r[i] = int(data2[i].split(" ")[1])
    d[i] = int(data2[i].split(" ")[2])

for i in range(m):
    for j in range(m):
        if r[i] == l[j]:
            r[i] = r[j]
            d[i] += d[j]

for i in range(m):
    for j in range(m):
        if l[i] == l[j] and r[i] == r[j] and d[i] != d[j]:
            print("No")
            flag = 1
            break
        elif l[i] == r[j] and r[i] == l[j] and d[i] != -d[j]:
            print("No")
            flag = 1
            break
    if flag == 1:
        break
if flag == 0:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
peak = [[] for i in range(N)]
vector = []
used = []
queue = []
amount = ["n" for k in range(N)]
for i in range(M):
    temp = [int(i) for i in input().split()]
    peak[temp[0]-1].append([temp[1],temp[2]*(-1)])
    peak[temp[1]-1].append([temp[0],temp[2]])
    vector.append(temp)


f = []

def check(a,c):
    if amount[a-1] == "n":
        amount[a-1] = c
        queue.append(a)
        return
    else:
        if c == amount[a-1]:
            return
        else:
            f.append(0)


for i in range(N):
    if f:
        break
    if amount[i] == "n":
        amount[i] = 0
        queue.append(i+1)
        while queue:
            if f:
                break
            a = queue.pop(0)
            for j in peak[a-1]:
                x,y = j[0],j[1]
                c = amount[a-1] + y
                check(x,c)
print("No" if f else "Yes")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
peak = [[] for i in range(N)]
vector = []
used = []
queue = []
amount = ["n" for k in range(N)]
for i in range(M):
    temp = [int(i) for i in input().split()]
    peak[temp[0]-1].append([temp[1],temp[2]*(-1)])
    peak[temp[1]-1].append([temp[0],temp[2]])
    vector.append(temp)


f = []

def check(a,c):
    if amount[a-1] == "n":
        amount[a-1] = c
        queue.append(a)
        return
    else:
        if c == amount[a-1]:
            return
        else:
            f.append(0)


for i in range(N):
    if amount[i] == "n":
        amount[i] = 0
        queue.append(i+1)
        while queue:
            a = queue.pop(0)
            for j in peak[a-1]:
                x,y = j[0],j[1]
                c = amount[a-1] + y
                check(x,c)
print("No" if f else "Yes")

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
import sys

inf = float("inf")
N, M = list(map(int, input().split()))
to = [[] for x in range(N+1)]
cost = [[] for x in range(N+1)]
value = [inf for x in range(N+1)]

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

for i in range(1, N+1):
    if value[i] != inf: continue
    
    value[i] = 0
    q = Queue()
    q.put(i)
    while not q.empty():
        tmp = q.get()
        for j in range(len(to[tmp])):
            nxt = to[tmp][j]
            nxt_val = value[tmp] + cost[tmp][j]
            if value[nxt] != inf:
                if value[nxt] == nxt_val: continue
                print("No")
                sys.exit()
            value[nxt] = nxt_val
            q.put(nxt)
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
import sys

inf = float("inf")

class Node:
    def __init__(self):
        self.to = []
        self.cost = []
        self.value = inf
        self.done = False

    def __str__(self):
        return "to = {0}, cost = {1}, value = {2}".format(self.to, self.cost, self.value)

N, M = list(map(int, input().split()))
I = [Node() for x in range(N+1)]

for i in range(M):
    l, r, d = list(map(int, input().split()))
    I[l].to.append(r)
    I[l].cost.append(d)
    I[r].to.append(l)
    I[r].cost.append(-d)

for i in I:
    if i.done: continue
    
    i.value = 0
    q = Queue()
    q.put(i)
    while not q.empty():
        tmp = q.get()
        for j in range(len(tmp.to)):
            nxt = I[tmp.to[j]]
            nxt_val = tmp.value + tmp.cost[j]
            if nxt.done:
                if nxt.value == nxt_val: continue
                print("No")
                sys.exit()
            nxt.value = nxt_val
            nxt.done = True
            q.put(nxt)
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

eq = [[0 for i in range(N+1)] for j in range(M)]
eq2 = [[0 for i in range(N)] for j in range(M)]
for i in range(M):
    eq[i][D[i][0]-1] = 1
    eq[i][D[i][1]-1] = -1
    eq[i][N] = D[i][2]
    eq2[i][D[i][0]-1] = 1
    eq2[i][D[i][1]-1] = -1
    
if(np.linalg.matrix_rank(eq) == np.linalg.matrix_rank(eq2)):
    print("Yes")
else:
    print("No")