結果

問題 No.1690 Power Grid
ユーザー lam6er
提出日時 2025-03-20 19:02:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 922 ms / 3,000 ms
コード長 2,197 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,276 KB
実行使用メモリ 140,792 KB
最終ジャッジ日時 2025-03-20 19:03:43
合計ジャッジ時間 12,317 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    n, m, k = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    INF = float('inf')
    
    # Initialize distance matrix
    d = [[INF] * n for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    
    # Read roads
    for _ in range(m):
        x, y, z = map(int, sys.stdin.readline().split())
        x -= 1
        y -= 1
        if d[x][y] > z:
            d[x][y] = z
            d[y][x] = z
    
    # Floyd-Warshall to compute all-pairs shortest paths
    for via in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][via] + d[via][j] < d[i][j]:
                    d[i][j] = d[i][via] + d[via][j]
    
    # Precompute bits for each mask
    mask_bits = [[] for _ in range(1 << n)]
    for mask in range(1 << n):
        bits = []
        tmp = mask
        s = 0
        while tmp:
            if tmp & 1:
                bits.append(s)
            tmp >>= 1
            s += 1
        mask_bits[mask] = bits
    
    # Initialize DP
    dp = [INF] * (1 << n)
    dp[0] = 0  # Start with no cities selected
    
    for mask in range(1 << n):
        if dp[mask] == INF:
            continue
        current_cnt = bin(mask).count('1')
        if current_cnt >= k:
            continue  # No need to proceed if already selected k
        
        # Try to add each city not in mask
        for j in range(n):
            if not (mask & (1 << j)):
                if mask == 0:
                    add_cost = A[j]
                else:
                    s_list = mask_bits[mask]
                    min_d = INF
                    for s in s_list:
                        min_d = min(min_d, d[j][s])
                    add_cost = A[j] + min_d
                new_mask = mask | (1 << j)
                if dp[new_mask] > dp[mask] + add_cost:
                    dp[new_mask] = dp[mask] + add_cost
    
    # Find the minimum cost with exactly k cities selected
    min_cost = INF
    for mask in range(1 << n):
        if bin(mask).count('1') == k and dp[mask] < min_cost:
            min_cost = dp[mask]
    
    print(min_cost)

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