結果

問題 No.2630 Colorful Vertices and Cheapest Paths
ユーザー hirayuu_ychirayuu_yc
提出日時 2024-02-16 21:44:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,744 ms / 2,500 ms
コード長 1,944 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 82,492 KB
実行使用メモリ 123,920 KB
最終ジャッジ日時 2024-09-28 19:59:07
合計ジャッジ時間 28,780 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 681 ms
88,656 KB
testcase_01 AC 1,387 ms
101,464 KB
testcase_02 AC 1,665 ms
120,000 KB
testcase_03 AC 70 ms
74,268 KB
testcase_04 AC 46 ms
63,064 KB
testcase_05 AC 71 ms
74,116 KB
testcase_06 AC 869 ms
84,316 KB
testcase_07 AC 1,525 ms
122,728 KB
testcase_08 AC 1,488 ms
118,136 KB
testcase_09 AC 1,519 ms
123,564 KB
testcase_10 AC 1,733 ms
123,920 KB
testcase_11 AC 1,705 ms
123,592 KB
testcase_12 AC 1,744 ms
123,504 KB
testcase_13 AC 1,702 ms
123,528 KB
testcase_14 AC 1,741 ms
123,640 KB
testcase_15 AC 1,445 ms
79,724 KB
testcase_16 AC 1,395 ms
79,792 KB
testcase_17 AC 1,467 ms
79,528 KB
testcase_18 AC 963 ms
91,368 KB
testcase_19 AC 1,242 ms
113,304 KB
testcase_20 AC 1,200 ms
107,300 KB
testcase_21 AC 1,240 ms
123,392 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
#sys.setrecursionlimit((1<<19)-1)
#import pypyjit
#pypyjit.set_param('max_unroll_recursion=-1')
input=sys.stdin.buffer.readline

from array import array
class UnionFind:
    def __init__(self,size:int)->None:
        self.siz=size
        self.tree=array("i",[-1]*size)
    
    def leader(self,pos:int)->int:
        ret=pos
        while self.tree[ret]>=0:
            ret=self.tree[ret]
        if pos!=ret:
            self.tree[pos]=ret
        return ret
    
    def same(self,u:int,v:int)->bool:
        return self.leader(u)==self.leader(v)
    
    def merge(self,u:int,v:int)->bool:
        u=self.leader(u)
        v=self.leader(v)
        if u==v:
            return False
        if self.tree[u]<self.tree[v]:
            u,v=v,u
        self.tree[v]+=self.tree[u]
        self.tree[u]=v
        return True
    
    def size(self,pos:int)->int:
        return -self.tree[self.leader(pos)]

    def groups(self)->list[list[int]]:
        mem=[[] for i in range(self.siz)]
        for i in range(self.siz):
            mem[self.leader(i)].append(i)
        ret=[]
        for i in mem:
            if len(i)!=0:
                ret.append(i)
        return ret

INF=(1<<61)-1
N,M=map(int,input().split())
edge=[]
for i in range(M):
    A,B=map(int,input().split())
    edge.append((A-1,B-1))
C=list(map(lambda x:int(x)-1,input().split()))
W=list(map(int,input().split()))
uni=[UnionFind(N) for i in range(1<<10)]
cost=[0]*(1<<10)
for i in range(1<<10):
    for j in range(10):
        if (i>>j)&1:
            cost[i]+=W[j]
    for a,b in edge:
        if (i>>(C[a]))&1 and (i>>(C[b]))&1:
            uni[i].merge(a,b)
Q=int(input())
for i in range(Q):
    u,v=map(int,input().split())
    u-=1
    v-=1
    ans=INF
    for j in range(1<<10):
        if (j>>(C[u]))&1 and (j>>(C[v]))&1:
            if uni[j].same(u,v):
                ans=min(ans,cost[j])
    if ans>=INF:
        print(-1)
    else:
        print(ans)
0