Submission #1500641

---

Source Code Expand

from collections import defaultdict

def bfs_sp(root, edges, n):
	cons = 10 * n + 1
	dis = [cons] * n
	# distance to itself is zero
	dis[root - 1] = 0
	queue = []
	queue.append(root)
	while len(queue)>0:
		# here the 0 in pop() is very important
		# which makes list as a queue
		end = queue.pop(0)
		for child in edges[end]:
			if dis[child-1]==cons:
				dis[child-1]=dis[end-1]+1
				queue.append(child)
	return dis


def splatter_painting():
	n, m = map(int, raw_input().split(" "))
	edges = defaultdict(list)
	for i in range(m):
		a = map(int, raw_input().split(" "))
		edges[a[0]].append(a[1])
		edges[a[1]].append(a[0])
	k = int(raw_input())
	q = []
	for i in range(k):
		q.append(map(int, raw_input().split(" ")))

	dic_root_distances = {}
	for i in range(n):
		dic_root_distances[i+1] = bfs_sp(i+1, edges, n)
	# print dic_root_distances

	ans = [0]*n
	for _q in reversed(q):
		dis = dic_root_distances[_q[0]]
		for i in range(n):
			if dis[i]<=_q[1] and ans[i]==0:
				ans[i] = _q[2]
		if 0 not in ans:
			break
	for c in ans:
		print c


if __name__ == "__main__":
	splatter_painting()

Submission Info

Judge Result