syuntoku14の進捗

進捗を書きなぐります

AOJでPythonに慣れる(6問目)

問題
Fastest Route
所感
pythonじゃ無理?
・正直わかんなかったのでリンク先をパクり参考にしました

コード
答えは出るけどRE(c++でやろう)

while True:
    N=int(input())
    if N==0:
        break
    
    stage=[]
    for i in range(N):
        stage.append(list(map(int,input().split())))
    
    INF=int(1e8)
    dp=[INF for i in range(1<<N)]
    dp[0]=0
    for bit in range(1<<N): #ステージのクリア状況分だけループを回す
        for i in range(N): 
            if bit & 1<<i:
                continue #iをクリアしている場合ループを抜ける
            cost=stage[i][0] #iをクリアするのに装備無しでかかる時間
            for j in range(N):
                if (bit & 1<<j)==0:
                    continue 
                cost=min(stage[i][j+1],cost) #jの装備を使ったときに速いほうを選択する
            now=(bit|(1<<i)) #iをクリアしたとする
            dp[now]=min(dp[now],dp[bit]+cost) #クリア状況bitの時にiをクリアした状態
    print(dp[(1<<N)-1])

参考元
kengo92i.hatenablog.jp