Problem:


Score : 400 points

Problem Statement

There are N people standing on the x-axis.
Let the coordinate of Person i be x_i.
For every i, x_i is an integer between 0 and 10^9 (inclusive).
It is possible that more than one person is standing at the same coordinate.

You will given M pieces of information regarding the positions of these people.
The i-th piece of information has the form (L_i, R_i, D_i).
This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_{R_i} - x_{L_i} = D_i holds.

It turns out that some of these M pieces of information may be incorrect.
Determine if there exists a set of values (x_1, x_2, ..., x_N) that is consistent with the given pieces of information.

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

1 \leq L_i, R_i \leq N (1 \leq i \leq M)

0 \leq D_i \leq 10 000 (1 \leq i \leq M)

L_i \neq R_i (1 \leq i \leq M)

If i \neq j, then (L_i, R_i) \neq (L_j, R_j) and (L_i, R_i) \neq (R_j, L_j).

D_i are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 D_1
L_2 R_2 D_2
:
L_M R_M D_M

Output

If there exists a set of values (x_1, x_2, ..., x_N) that is consistent with all given pieces of information, print Yes; if it does not exist, print No.

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

Some possible sets of values (x_1, x_2, x_3) are (0, 1, 2) and (101, 102, 103).

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

If the first two pieces of information are correct, x_3 - x_1 = 2 holds, which is contradictory to the last piece of information.

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



Sample input:
3 3
1 2 1
2 3 1
1 3 2


Sample output:
Yes

Submission status: Runtime Error

Solution code:
pos = [[] for i in range(100010)]
por = [[] for s in range(100010)]
posvis = [1 for y in range(200010)]
qe = []
n, m = map(int, input().split())
for i in range(m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])
    qe.append([l, r, i])
 
 
def deep(self):
    for j in pos[self]:
        if posvis[j[2]]:
            posvis[j[2]] = 0
            if len(por[self]) < 1:
                por[self] = [100000]
            if len(set(por[self])) > 1:
                print("No")
                exit()
            por[j[0]].append(por[self][0] + j[1])
            deep(j[0])
for qww in qe:
    if posvis[qww[2]]:
        deep(qww[0])
for i in por:
    if i:
        if len(set(i)) > 1:
            print("No")
            exit()
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
pos = [[] for i in range(100001)]
por = [[] for s in range(200001)]
posvis = [1 for y in range(200001)]
qe = []
n, m = map(int, input().split())
for i in range(m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])
    qe.append([l, r, i])
 
 
def deep(self):
    for j in pos[self]:
        if posvis[j[2]]:
            posvis[j[2]] = 0
            if len(por[self]) < 1:
                por[self] = [100000]
            if len(set(por[self])) > 1:
                print("No")
                exit()
            print(len(por[self]))
            por[j[0]].append(por[self][0] + j[1])
            deep(j[0])
for qww in qe:
    if posvis[qww[2]]:
        deep(qww[0])
for i in por:
    if i:
        if len(set(i)) > 1:
            print("No")
            exit()
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
pos = [[] for i in range(100000)]
por = [[] for s in range(200000)]
posvis = [1 for y in range(200000)]
qe = []
n, m = map(int, input().split())
for i in range(m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])
    qe.append([l, r, i])
 
 
def deep(self):
    for j in pos[self]:
        if posvis[j[2]]:
            posvis[j[2]] = 0
            if len(por[self]) < 1:
                por[self] = [100000]
            if len(set(por[self])) > 1:
                print("No")
                exit()
            por[j[0]].append(por[self][0] + j[1])
            deep(j[0])
for qww in qe:
    if posvis[qww[2]]:
        deep(qww[0])
for i in por:
    if i:
        if len(set(i)) > 1:
            print("No")
            exit()
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
pos = [[] for i in range(100000)]
por = [[] for s in range(200000)]
posvis = [1 for y in range(200000)]
qe = []
n, m = map(int, input().split())
for i in range(m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])
    qe.append([l, r, d])
 
 
def deep(self):
    for j in pos[self]:
        if posvis[j[2]]:
            posvis[j[2]] = 0
            if len(por[self]) < 1:
                por[self] = [100000]
            if len(set(por[self])) > 1:
                print("No")
                exit()
            if len(por[j[0]]) < 1:
                por[j[0]] = [100000]
            por[j[0]].append(por[self][0] + j[1])
            deep(j[0])
for qww in qe:
    if posvis[qww[0]]:
        deep(qww[0])
for i in por:
    if i:
        if len(set(i)) > 1:
            print("No")
            exit()
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
pos = [[] for i in range(100000)]
por = [[] for s in range(200000)]
posvis = [1 for y in range(200000)]
qe = []
n, m = map(int, input().split())
for i in range(m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])
    qe.append([l, r, d])
 
 
def deep(self):
    for j in pos[self]:
        if posvis[j[2]]:
            posvis[j[2]] = 0
            if len(por[self]) < 1:
                por[self] = [100000]
            if len(set(por[self])) > 1:
                print("No")
                exit()
                por[j[0]].append(por[self][0] + j[1])
            por[j[0]].append(por[self][0] + j[1])
            deep(j[0])
for qww in qe:
    if posvis[qww[0]]:
        deep(qww[0])
for i in por:
    if i:
        if len(set(i)) > 1:
            print("No")
            exit()
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
pos = [[] for i in range(100000)]
por = [[] for s in range(200000)]
posvis = [1 for y in range(200000)]
qe = []
n, m = map(int, input().split())
for i in range(m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])
    qe.append([l, r, d])
 
 
def deep(self, vis=1):
    for j in pos[self]:
        if posvis[j[2]]:
            posvis[j[2]] = 0
            if vis:
                por[self] = [100000]
            if len(set(por[self])) > 1:
                print("No")
                exit()
                por[j[0]].append(por[self][0] + j[1])
            por[j[0]].append(por[self][0] + j[1])
            deep(j[0], 0)
for qww in qe:
    if posvis[qww[0]]:
        deep(qww[0])
for i in por:
    if i:
        if len(set(i)) > 1:
            print("No")
            exit()
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
pos = [[] for i in range(100000)]
por = [[] for s in range(200000)]
posvis = [[1] for y in range(100000)]
qe = []
n, m = map(int, input().split())
for i in range(m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])
    qe.append([l, r, d])


def deep(self, vis=1):
    for j in pos[self]:
        if posvis[j[2]]:
            posvis[j[2]] = 0
            if vis:
                por[self] = [100000]
            if len(set(por[self])) > 1:
                print("No")
                exit()
                por[j[0]].append(por[self][0] + j[1])
            por[j[0]].append(por[self][0] + j[1])
            deep(j[0], 0)

for qww in qe:
    if posvis[qww[0]]:
        deep(qww[0])
for i in por:
    if i:
        if len(set(i)) > 1:
            print("No")
            exit()
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
pos = [[] for i in range(100000)]
por = [[] for s in range(200000)]
posvis = [[1] for y in range(100000)]
qe = []
n, m = map(int, input().split())
for i in range(m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])
    qe.append([l, r, d])
 
 
def deep(self, vis=1):
    for j in pos[self]:
        if posvis[j[2]]:
            posvis[j[2]] = 0
            if vis:
                por[self] = [100000]
            if len(set(por[self])) > 1:
                print("No")
                exit()
                por[j[0]].append(por[self][0] + j[1])
            por[j[0]].append(por[self][0] + j[1])
            deep(j[0], 0)
for qww in qe:
    if posvis[qww[0]]:
        deep(qww[0])
for i in por:
    if i:
        if len(set(i)) > 1:
            print("No")
            exit()
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####

def main():
	N,M = LI()

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

	dist = [[] for _ in range(N)]
	memo = dict()
	s = float('inf')

	for m in range(M):
		L,R,D = LI()
		L -= 1; R -= 1

		dist[L].append((R,D))
		dist[R].append((L,-D))

		s = min(s, L, R)

	memo[s] = 0

	for i in range(len(dist)):
		for v, d in dist[i]:

			if v in memo:
				f = memo[v] == memo[i] + d
				if not f:
					print("No")
					exit()
			else:
				memo[v] = memo[i] + d

	print("Yes")




if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####

def main():
	N,M = LI()

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

	dist = [[] for _ in range(N)]
	memo = dict()
	s = float('inf')

	for m in range(M):
		L,R,D = LI()
		L -= 1; R -= 1

		dist[L].append((R,D))
		dist[R].append((L,-D))

		s = min(s, L)

	memo[s] = 0

	for i in range(len(dist)):
		for v, d in dist[i]:
	
			if v in memo:
				f = memo[v] == memo[i] + d
				if not f:
					print("No")
					exit()
			else:
				memo[v] = memo[i] + d

	print("Yes")




if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####

def main():
	N,M = LI()

	if M == 0:
		print("Yes")
		exit()
		
	dist = [[] for _ in range(N)]
	memo = dict()
	s = float('inf')

	for m in range(M):
		L,R,D = LI()
		L -= 1; R -= 1

		dist[L].append((R,D))
		dist[R].append((L,-D))

		s = min(s, L)

	memo[s] = 0

	for i in range(s,len(dist)):
		for v, d in dist[i]:
	
			if v in memo:
				f = memo[v] == memo[i] + d
				if not f:
					print("No")
					exit()

			else:
				memo[v] = memo[i] + d

	print("Yes")




if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####

def main():
	N,M = LI()

	dist = [[] for _ in range(N)]
	memo = dict()
	s = float('inf')

	for m in range(M):
		L,R,D = LI()
		L -= 1; R -= 1

		dist[L].append((R,D))
		dist[R].append((L,-D))

		s = min(s, L)

	memo[s] = 0

	for i in range(s,len(dist)):
		for v, d in dist[i]:
	
			if v in memo:
				f = memo[v] == memo[i] + d
				if not f:
					print("No")
					exit()

			else:
				memo[v] = memo[i] + d

	print("Yes")




if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####

def main():
	N,M = LI()

	dist = [[] for _ in range(N)]
	memo = dict()
	s = float('inf')
	
	for m in range(M):
		L,R,D = LI()
		L -= 1; R -= 1

		dist[L].append((R,D))
		dist[R].append((L,-D))

		s = min(s, L)

	memo[s] = 0

	for i in range(len(dist)):
		for v, d in dist[i]:
	
			if v in memo:
				f = memo[v] == memo[i] + d
				if not f:
					print("No")
					exit()

			else:
				memo[v] = memo[i] + d

	print("Yes")




if __name__ == '__main__':
	main()

Submission status: Runtime Error

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

pos = []
for a in range(100001):
  pos.append([a,0])

def check(i):
  k,x = pos[i]
  if k != i:
    k2,x2 = check(k)
    pos[i] = [k2,x+x2]
  return pos[i]

for a in range(m):
  l,r,d = map(int,raw_input().split(" "))

  lk,lx = check(l)
  rk,rx = check(r)

  if lk != rk:
    t = d+lx-rx
    if t >= 0:
      pos[rk] = (lk,t)
    else:
      pos[lk] = (rk,-t)
  else:
    if rx - lx != d:
      print "No"
      exit(0)
print "Yes"



  if l > r:
    data.append([r,l,-d])
  else:
    data.append([l,r,d])
data.sort()

Submission status: Runtime Error

Solution code:
MAX = 10**9


class UnionFindTree:
    def __init__(self, parent):
        self.__parent = parent

    @property
    def parent(self):
        return self.__parent

    def find(self, x, merge):
        root_x, info_x = self.__parent[x]
        if root_x != x:
            r, i = self.find(root_x, merge)
            self.__parent[x] = [r, merge(info_x, i)]
        return self.__parent[x]

    def merge(self, x, y, func):
        root_x, info_x = self.find(x, func)
        root_y, info_y = self.find(y, func)
        if root_x != root_y:
            self.__parent[y] = [root_x, func(info_x, info_y)]

    def cluster(self, func):
        result = {}
        for x in self.__parent.keys():
            root, info = self.find(x, func)
            if root not in result:
                result[root] = info
            elif result[root] is not info:
                result[root] = merge(result[root], info)
        return result


class MergeError(Exception):
    pass


def merge(x, y):
    sx = set(x)
    sy = set(y)
    xy = sx & sy
    diff = None
    d = x.copy()
    for key in sx & sy:
        xv = x[key]
        yv = y[key]
        if diff is None:
            diff = xv - yv
        if xv != yv + diff:
            raise MergeError()
    for key in sy - sx:
        d[key] = y[key] + diff
    return d


def main():
    n, m = map(int, input().split())
    info = []
    for _ in range(m):
        l, r, d = map(int, input().split())
        info.append([l, r, d])
    info.sort()
    min_x = None
    max_x = None
    c = UnionFindTree({i: [i, {i: 0}] for i in range(1, n+1)})
    for l, r, d in info:
        try:
            cl, xl = c.find(l, merge)
            cr, xr = c.find(r, merge)
        except MergeError:
            print('No')
            return
        if cl == cr:
            if xl[l] + d != xl[r]:
                print('No')
                return
        else:
            xl[r] = xl[l] + d
            xr[l] = xr[r] - d
            try:
                c.merge(l, r, merge)
            except MergeError:
                print('No')
                return
    try:
        c.cluster(merge)
    except MergeError:
        print('No')
        return
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
pos = [[] for i in range(100000)]
por = [[] for s in range(200000)]
posvis = [[1] for y in range(100000)]
qe = [[] for i in range(2)]
n, m = map(int, input().split())
for i in range(m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])

print("Yes")

Submission status: Runtime Error

Solution code:
import heapq
import sys
from collections import deque

class node_data():
    def __init__(self, to, dist):
        self.to = to
        self.dist = dist
    def __lt__(self,other):
        return (self.dist) < (other.dist)

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def prim(graph, N):
    node_queue = []
    done_list = [False] * (N + 1)
    done_list[0] = True
    first = graph.keys()[0]
    done_list[first] = True
    for nd in graph[first]:
        heapq.heappush(node_queue, nd)

    min_dist = 0
    while all(done_list) == False:
        if len(node_queue) <= 0:
            k = done_list.index(False)
            for nd in graph[k]:
                heapq.heappush(node_queue, nd)
            done_list[k] = True
        nd = heapq.heappop(node_queue)
        done_list[nd.to] = True
        min_dist += nd.dist
        if nd.to in graph:
            for  new_nd in graph[nd.to]:
                #if done_list[new_nd.to] == True:
                    heapq.heappush(node_queue, new_nd)
    return min_dist

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    sum_D = 0
    for i in range(M):
        input_raw = read_func().strip().split()
        [L, R, D] = [int(input_raw[0]), int(input_raw[1]),int(input_raw[2])]
        sum_D += D
        if L in graph:
            graph[L].append(node_data(R, D))
        else:
            graph[L] = [node_data(R, D)]

    min_dist = prim(graph, N)
    if sum_D/2 + sum_D % 2 == min_dist:
        print "Yes"
    else:
        print "No"

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
pos = [[] for i in range(100000)]
por = [[] for s in range(200000)]
posvis = [[1] for y in range(100000)]
qe = [[] for i in range(2)]
n, m = map(int, input().split())
for i in range(m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])
    qe.append([l, r, d])


def deep(self, vis=1):
    for j in pos[self]:
        if posvis[j[2]]:
            posvis[j[2]] = 0
            if vis:
                por[self] = [100000]
            if len(set(por[self])) > 1:
                print("No")
                exit()
                por[j[0]].append(por[self][0] + j[1])
            por[j[0]].append(por[self][0] + j[1])
            deep(j[0], 0)
for qww in qe:
    if posvis[qww[0]]:
        deep(qww[0])
for i in por:
    if i:
        if len(set(i)) > 1:
            print("No")
            exit()
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
def LI(): return list(map(int, input().split()))
def LS(): return input().split()
def I(): return int(input())
def S(): return input()

import networkx as nx

n, m = LI()
l = []
for i in range(m):
    l.append(LI())
edge = []
graph1 = [[float("inf")]*n for i in range(n)]
graph2 = [[float("inf")]*n for i in range(n)]
dic1 = {}
dic2 = {}
for i in range(m):
    if l[i][0]-1 not in dic1:
       dic1[l[i][0]-1] = 1
    else:
        dic1[l[i][0]-1] += 1
    if l[i][1]-1 not in dic2:
       dic2[l[i][1]-1] = 1
    else:
        dic2[l[i][1]-1] += 1 
    edge.append([l[i][0], l[i][1]])
    graph1[l[i][0] - 1][l[i][1] - 1] = l[i][2]
    graph2[l[i][0] - 1][l[i][1] - 1] = -l[i][2]
G = nx.DiGraph()
G.add_edges_from(edge)
try:
    a = nx.topological_sort(G)
except:
    print("No")
    exit()
# print(a)

# 向きありグラフ
# 矛盾する時、距離正の閉路が存在(1→3, 3と３→1, 2)、距離を持つ(i,j)に対して全てのパスの距離が違う(最小 != 最大 1→2→3 1→4→3)
# グラフを作った後、前者はトポロジカルソート、 後者はダイクストラと、最長距離は辺の値を負にするためダイクストラが使えない?→いや使える全部負ならok

# 閉路が無い時、1→3→5 と1→4→5 を判定できない(V^3)
# ２つ以上のパスを持つところをリストでもっておいて探索
s = []
e = []
for i in dic1.keys():
    if dic1[i] > 1:
        s.append(i)
for i in dic2.keys():
    if dic2[i] > 1:
        e.append(i)
# print(s,e)

import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば，始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

flag = True
for i in s:
    test = Dijkstra()
    k1 = test.dijkstra(graph1,i)
    k2 = test.dijkstra(graph2, i)
    for j in e:
        if abs(k1[j]) != abs(k2[j]):
            flag = False
            print("No")
            exit()
            break
    if flag == False:
        break
if flag:
    print("Yes")

Submission status: Runtime Error

Solution code:
pos = [[] for i in range(100000)]
por = [[] for s in range(200000)]
posvis = [[1] for y in range(100000)]
qe = []
n, m = map(int, input().split())
for i in range(m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])
    qe.append([l, r, d])

print("Yes")

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = collections.defaultdict(list)
    for _ in range(m):
        l,r,d = LI()
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if b[i] != False:
            if c == False:
                return True
            return b[i] == c
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for _ in range(m):
        l,r,d = LI()
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if b[i] != False:
            if c == False:
                return True
            return b[i] == c
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Runtime Error

Solution code:
import sys,time
sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    e = [[] for _ in range(n)]
    for _ in range(m):
        l,r,d = LI()
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if time.time() - start > 0.9:
            return 'Yes'
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Runtime Error

Solution code:
import sys,time
sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    e = [[] for _ in range(n)]
    for _ in range(m):
        l,r,d = LI()
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if b[r] != False:
                if b[r] != c+d:
                    return False
            else:
                if not g(r,c+d):
                    return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        gt = time.time() - start
        if gt > 0.9:
            return True
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())

Submission status: Runtime Error

Solution code:
pos = [[] for i in range(100000)]
por = [[] for s in range(200000)]
posvis = [[1] for y in range(100000)]
qe = []
n, m = map(int, input().split())
if m == 0:
    print("Yes")
    exit()
for i in range(m):
    l, r, d = map(int, input().split())
    pos[l].append([r, d, i])
    pos[r].append([l, -d, i])
    qe.append([l, r, d])
def deep(self, vis = 0):
    for j in pos[self]:
        if posvis[j[2]]:
            posvis[j[2]] = 0
            if not vis:
                por[self] = [100000]
            if len(set(por[self])) > 1:
                print("No")
                exit()
                por[j[0]].append(por[self][0] + j[1])
            por[j[0]].append(por[self][0] + j[1])
            deep(j[0], 1)
for qww in qe:
    if posvis[qww[0]]:
        deep(qww[0])
for i in por:
    if i:
        if len(set(i)) > 1:
            print("No")
            exit()
else:
    print("Yes")