結果

問題 No.1690 Power Grid
コンテスト
ユーザー ntuda
提出日時 2025-08-10 22:31:05
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,037 bytes
コンパイル時間 285 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 67,648 KB
最終ジャッジ日時 2025-08-10 22:31:09
合計ジャッジ時間 3,636 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import combinations
from atcoder.dsu import DSU
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
XYZ = [list(map(int,input().split())) for _ in range(M)]
INF = 10 ** 11
cost = [[INF] * N for _ in range(N)]
for i in range(N):
    cost[i][i] = 0
for x,y,z in XYZ:
    x -= 1
    y -= 1
    cost[x][y] = z
    cost[y][x] = z
for k in range(N):
    for i in range(N):
        for j in range(N):
            if cost[i][k]!=INF and cost[k][j]!=INF:
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
Q = []
for i in range(N):
    for j in range(i+1,N):
        Q.append((cost[i][j],i,j))
Q.sort()

ans = INF
for C in combinations(range(N),K):
    tmp = 0
    C = set(C)
    for c in C:
        tmp += A[c]
    dsu = DSU(N)
    cnt = 0
    for c,a,b in Q:
        if a in C and b in C:
            if dsu.same(a,b):
                continue
            dsu.merge(a,b)
            tmp += c
            cnt += 1
            if cnt == K:
                break
    ans = min(ans,tmp)

print(ans)
0