fork download
copy 
  1. import sys
  2. sys.setrecursionlimit(10**6)
  3. from collections import defaultdict
  4.  
  5. class Graph:
  6. 	def __init__(self,n):
  7. 		self.v=n 
  8. 		self.d=defaultdict(lambda:[])
  9. 		self.tc=[[-1 for i in range(n)] for i in range(n)] #To store weights for every i to j
  10. 		self.tmp=[[0 for i in range(n)] for i in range(n)] #To store girven weight from i to j
  11.  
  12. 	def add_edge(self,u,v,w):
  13. 		self.d[u-1].append(v-1)
  14. 		self.d[v-1].append(u-1)
  15. 		self.tmp[u-1][v-1]=self.tc[v-1][u-1]=w
  16.  
  17.  
  18. 	def dfs(self,src,dst,wt):
  19.  
  20. 		self.tc[src][dst]=wt
  21. 		self.tc[dst][src]=wt
  22.  
  23. 		for i in self.d[dst]:
  24. 			if self.tc[src][i]==-1:
  25. 				self.dfs(src,i,wt+self.tmp[dst][i])
  26.  
  27.  
  28. 	def transclosure(self):
  29.  
  30. 		mod=10**9 +7
  31.  
  32. 		for i in range(self.v):
  33. 			self.dfs(i,i,0)
  34.  
  35. 		# for i in self.tc:
  36. 		# 	print(*i)
  37.  
  38.  
  39. 		sume=0
  40.  
  41. 		for i in range(self.v):
  42. 			sume=(sume+sum(self.tc[i][i+1:])%mod)%mod
  43.  
  44. 		return sume 
  45.  
  46.  
  47. 	def clear(self):
  48. 		self.tc.clear()
  49. 		self.d.clear()
  50.  
  51.  
  52. for _ in range(int(input())):
  53. 	n=int(input())
  54. 	g=Graph(n)
  55.  
  56.  
  57. 	for _ in range(n-1):
  58. 		u,v,w =map(int,input().split())
  59. 		g.add_edge(u,v,w)
  60.  
  61. 	#g.printf()
  62. 	res=g.transclosure()
  63. 	print(res)
  64. 	g.clear()
Success #stdin #stdout 0.02s 9260KB
comments (?)
stdin
copy 
1
4
1 2 1
2 3 2
3 4 3
stdout
copy 
20
https://ideone.com/UqBH3u
language:
Python 3 (python  3.12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!