結果
問題 | No.1207 グラフX |
ユーザー |
|
提出日時 | 2020-08-30 14:32:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,028 ms / 2,000 ms |
コード長 | 1,655 bytes |
コンパイル時間 | 224 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 173,276 KB |
最終ジャッジ日時 | 2024-11-15 07:42:09 |
合計ジャッジ時間 | 33,947 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
N, M, X = map(int, input().split())XYZ = []p = 10 ** 9 + 7class UnionFind:def __init__(self, N):self.N = Nself.P = [-1] * Ndef Find(self, x):if self.P[x] < 0:return xelse:self.P[x] = self.Find(self.P[x])return self.P[x]def query(self, x, y):x -= 1y -= 1x = self.Find(x)y = self.Find(y)if x == y:return Falseif self.P[x] > self.P[y]:x, y = y, xself.P[x], self.P[y] = self.P[x] + self.P[y], xreturn TrueG = UnionFind(N)for i in range(M):x, y, z = map(int, input().split())XYZ += [[z, x, y]]XYZ.sort()E = []V1 = [[] for i in range(N)]for z, x, y in XYZ:if G.query(x, y):E += [[x - 1, y - 1, z]]V1[x - 1] += [y - 1]V1[y - 1] += [x - 1]que = [0]P = [-1] * NP[0] = 0V = [[] for i in range(N)]while que:q = que.pop()for v in V1[q]:if P[v] == -1:V[q] += [v]P[v] = qque += V[q]A = [1] * Nque = [0]while que:q = que.pop()if V[q]:que += [V[q].pop()]else:if q == 0:breakA[P[q]] += A[q]que += [P[q]]ans = 0for x, y, z in E:if P[x] != y:x, y = y, xans += A[x] * (N - A[x]) % p * pow(X, z, p) % pans %= pprint(ans)