結果

問題 No.2591 安上がりな括弧列
ユーザー anonymouslyanonymously
提出日時 2023-12-19 17:18:03
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 1,397 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 262,336 KB
最終ジャッジ日時 2024-09-27 08:55:54
合計ジャッジ時間 4,221 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
17,824 KB
testcase_01 AC 32 ms
10,880 KB
testcase_02 AC 36 ms
11,008 KB
testcase_03 AC 31 ms
10,880 KB
testcase_04 AC 31 ms
11,008 KB
testcase_05 AC 31 ms
11,008 KB
testcase_06 AC 31 ms
10,880 KB
testcase_07 AC 31 ms
11,008 KB
testcase_08 AC 49 ms
12,544 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます

ソースコード

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