結果

問題 No.3312 Fire Engine
コンテスト
ユーザー LyricalMaestro
提出日時 2025-10-29 22:31:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 411 ms / 2,000 ms
コード長 1,096 bytes
コンパイル時間 502 ms
コンパイル使用メモリ 82,844 KB
実行使用メモリ 90,516 KB
最終ジャッジ日時 2025-10-29 22:31:21
合計ジャッジ時間 11,710 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/3312

MAX_VALUE = 10 ** 18

def main():
    N = int(input())
    D = []
    for _ in range(N):
        D.append(list(map(int, input().split())))


    weights = [0] * (2 ** N)
    for bit in range(1, 2 ** N):
        cont = 0
        for i in range(N):
            if (1 << i) & bit > 0:
                cont += 1

        weight = N - cont
        weights[bit] = weight

    dp = [[MAX_VALUE] * N for _ in range(2 ** N)]
    dp[1][0] = 0
    for bit in range(1, 2 ** N):
        for from_i in range(N):
            if bit & (1 << from_i) == 0:
                continue
            d0 = dp[bit][from_i]

            for to_i in range(N):
                if bit & (1 << to_i) == 0:
                    new_bit = bit + (1 << to_i)
                    d = D[from_i][to_i]
                    new_d = d * weights[bit] + d0
                    dp[new_bit][to_i] = min(dp[new_bit][to_i], new_d)

    answer = MAX_VALUE
    for i in range(N):
        answer = min(answer, dp[-1][i])
    print(answer)










                


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