結果
問題 | No.1690 Power Grid |
ユーザー |
|
提出日時 | 2021-09-24 22:28:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 738 ms / 3,000 ms |
コード長 | 922 bytes |
コンパイル時間 | 280 ms |
コンパイル使用メモリ | 82,312 KB |
実行使用メモリ | 78,816 KB |
最終ジャッジ日時 | 2024-07-05 10:55:48 |
合計ジャッジ時間 | 13,078 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
n,m,k = map(int,input().split()) A = list(map(int,input().split())) inf = 10**12 dis = [[inf]*n for i in range(n)] for i in range(n): dis[i][i] = 0 for i in range(m): x,y,z = map(int,input().split()) x,y = x-1,y-1 dis[x][y] = dis[y][x] = z for t in range(n): for i in range(n): for j in range(n): if dis[i][t] == inf or dis[t][j] == inf: continue dis[i][j] = min(dis[i][j],dis[i][t]+dis[t][j]) dp = [inf]*(1<<n) for i in range(n): dp[1<<i] = A[i] ans = inf for i in range(1<<n): if dp[i] == inf: continue if bin(i).count("1") == k: ans = min(ans,dp[i]) for j in range(n): if i >> j & 1: continue cost = dp[i]+A[j] d = inf for t in range(n): if i >> t & 1: d = min(d,dis[t][j]) cost += d dp[i|1<<j] = min(dp[i|1<<j],cost) print(ans)