結果
問題 | No.1207 グラフX |
ユーザー |
|
提出日時 | 2020-08-30 15:05:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,722 ms / 2,000 ms |
コード長 | 1,734 bytes |
コンパイル時間 | 322 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 390,724 KB |
最終ジャッジ日時 | 2024-12-07 03:35:29 |
合計ジャッジ時間 | 32,551 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
class UnionFind():def __init__(self, n):self.n = nself.parents = [-1] * ndef find(self, x):if self.parents[x] < 0:return xelse:self.parents[x] = self.find(self.parents[x])return self.parents[x]def union(self, x, y):x = self.find(x)y = self.find(y)if x == y:returnif self.parents[x] > self.parents[y]:x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xdef same(self, x, y):return self.find(x) == self.find(y)def roots(self):return [i for i, x in enumerate(self.parents) if x < 0]def num_roots(self):return len([i for i, x in enumerate(self.parents) if x < 0])def members(self, x):root = self.find(x)return [i for i in range(self.n) if self.find(i) == root]def num_members(self,x):return abs(self.parents[self.find(x)])def __str__(self):return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())N, M, X = map(int, input().split())A = [list(map(int, input().split())) for _ in range(M)]uf = UnionFind(N)edge = [[] for _ in range(N)]e_length = [0]*(N-1)num = 0for x,y,z in A:x -= 1y -= 1if not uf.same(x,y):uf.union(x,y)e_length[num] = zedge[x].append((y,num))edge[y].append((x,num))num += 1if num==N-1:breakimport syssys.setrecursionlimit(10**8)def dfs(v):ans = 0for u,num in edge[v]:if used[num]==False:used[num] = Truev_num = dfs(u)e_cnt[num] = v_num*(N-v_num)ans += v_numreturn ans+1e_cnt = [0]*(N-1)used = [False]*(N-1)dfs(0)mod = 10**9+7ans = 0for i in range(N-1):ans += e_cnt[i]*pow(X,e_length[i],mod)ans %= modprint(ans)