結果

問題 No.1207 グラフX
コンテスト
ユーザー ああ
提出日時 2026-05-18 18:48:46
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 553 ms / 2,000 ms
コード長 780 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 325 ms
コンパイル使用メモリ 84,992 KB
実行使用メモリ 138,112 KB
最終ジャッジ日時 2026-05-18 18:49:15
合計ジャッジ時間 20,416 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

def aa(m):
    c=[]
    while m!=uf[m]:
        c.append(m);m=uf[m]
    for i in c:
        uf[i]=m
    return m
ans=0
n,m,X=map(int,input().split());mod=10**9+7
uf=[i for i in range(n)]
v=[[] for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split());a-=1;b-=1
    x,y=aa(a),aa(b)
    if x==y:
        continue
    uf[x]=y;c=pow(X,c,mod)
    v[a].append((b,c));v[b].append((a,c))
f=deque([(0,0,0)]);x=[1]*n
while f:
    q,w,e=f.pop()
    if len(v[q])>e:
        f.append((q,w,e+1))
        if v[q][e][0]!=w:
            f.append((v[q][e][0],q,0))
    else:
        c=0
        for i,j in v[q]:
            if i==w:
                c=j
                continue
            x[q]+=x[i]
        ans+=x[q]*(n-x[q])%mod*c%mod
print(ans%mod)
0