結果
問題 | No.1207 グラフX |
ユーザー |
![]() |
提出日時 | 2020-08-30 13:34:21 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 421 ms / 2,000 ms |
コード長 | 1,678 bytes |
コンパイル時間 | 3,634 ms |
コンパイル使用メモリ | 171,104 KB |
実行使用メモリ | 35,200 KB |
最終ジャッジ日時 | 2024-11-15 06:49:57 |
合計ジャッジ時間 | 16,870 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include "bits/stdc++.h"using namespace std;class UnionFind {private:vector<int> Rank, Vol, Root;public:UnionFind(int N) : Rank(N, 1), Vol(N, 1), Root(N) {for (int i = 0; i < N; i++) Root[i] = i;}int Find(int N) { return (N == Root[N] ? N : Root[N] = Find(Root[N])); }bool Same(int X, int Y) { return Find(X) == Find(Y); }void Union(int X, int Y) {X = Find(X), Y = Find(Y);if (X == Y) return;if (Rank[X] > Rank[Y]) Root[X] = Y, Vol[Y] += Vol[X];else if (Rank[X] < Rank[Y]) Root[Y] = X, Vol[X] += Vol[Y];else Root[Y] = X, Vol[X] += Vol[Y], Rank[X]++;}int Size(int N) { return Vol[Find(N)]; }};constexpr long long MOD = 1000000007;long long Pow(long long A, long long B) {if (B == 0) return 1;if (B % 2 == 0) {long long C = Pow(A, B / 2);return (C * C) % MOD;}return (A * Pow(A, B - 1)) % MOD;}vector<pair<int, int> > Par;vector<vector<pair<int, int> > > V;vector<long long> Size;void DFS(int P) {Size[P] = 1;for (pair<int, int> NP : V[P]) {if (Par[NP.first].first == -2) {Par[NP.first] = { P, NP.second };DFS(NP.first);Size[P] += Size[NP.first];}}}int main() {long long N, M;long long X;cin >> N >> M >> X;UnionFind UF(N);V.resize(N);for (int i = 0; i < M; i++) {int S, T;long long Z;cin >> S >> T >> Z;S--, T--;if (!UF.Same(S, T)) {V[S].push_back({ T, Z });V[T].push_back({ S, Z });UF.Union(S, T);}}Size.resize(N);Par.assign(N, { -2, -1 });Par[0] = { -1, 0 };DFS(0);long long ANS = 0;for (int i = 1; i < N; i++) {ANS += (Pow(X, Par[i].second) * ((Size[i] * (N - Size[i])) % MOD)) % MOD;ANS %= MOD;}cout << ANS << endl;}