結果

問題 No.2591 安上がりな括弧列
コンテスト
ユーザー anonymously
提出日時 2023-12-19 17:18:03
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,397 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 262,336 KB
最終ジャッジ日時 2024-09-27 08:55:54
合計ジャッジ時間 4,221 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

# coding: utf-8
import heapq

def isValid(S):
    a=0
    for c in S:
        if c=='(':
            a+=1
        elif c==')':
            a-=1
        else:
            raise Exception
        if a<0:
            return False
    return a==0    

def change(S,i):
    L=list(S)
    if S[i]=='(':
        L[i]=')'
    elif S[i]==')':
        L[i]='('
    else:
        raise Exception
    return "".join(L)

def dijkstra(n,S,A):
    N=2*n
    if len(S)!=N or len(A)!=N:
        raise Exception
    closed=set()
    temp={}
    heap=[]
    heapq.heappush(heap,(0,S))
    while heap:
        tupl=heapq.heappop(heap)
        T=tupl[1]
        cost=tupl[0]
        if T not in closed:
            closed.add(T)
            if(isValid(T)):
                return cost
            for i in range(N):
                if i==0 and T[i]=='(':
                    continue
                elif i==N-1 and T[i]==')':
                    continue
                elif T[i]!=S[i]:
                    continue
                U=change(T,i)
                if U not in closed:
                    if U not in temp:
                        temp[U]=cost+A[i]
                    else:
                        temp[U]=min(temp[U],cost+A[i])
                    heapq.heappush(heap,(temp[U],U))
    raise Exception

if __name__ == "__main__":
    print(dijkstra(int(input()),input(),list(map(int,input().split()))))
0