結果

問題 No.3079 Unite Japanese Prefectures
ユーザー 👑 binap
提出日時 2025-03-29 08:02:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,128 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 62,916 KB
最終ジャッジ日時 2025-03-29 08:02:10
合計ジャッジ時間 2,726 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 9 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input_data = sys.stdin.read().strip().split()
    if not input_data:
        return
    it = iter(input_data)
    N = int(next(it))
    M = int(next(it))
    
    # 道路候補のリスト．各候補は (重み, u, v) として格納する．
    # ここで重み = 6/(7-C) となる．
    edges = []
    for _ in range(M):
        u = int(next(it))
        v = int(next(it))
        c = int(next(it))
        weight = 6 / (7 - c)
        # インデックスは 0-indexed にする
        edges.append((weight, u - 1, v - 1))
    
    # Kruskal法のため重みでソート
    edges.sort(key=lambda x: x[0])
    
    parent = list(range(N))
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    total_expectation = 0.0
    count = 0
    for w, u, v in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            total_expectation += w
            count += 1
            if count == N - 1:
                break
    
    print(total_expectation)

if __name__ == '__main__':
    main()
0