結果

問題 No.2630 Colorful Vertices and Cheapest Paths
ユーザー hirayuu_ychirayuu_yc
提出日時 2024-02-16 21:44:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,767 ms / 2,500 ms
コード長 1,944 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 123,096 KB
最終ジャッジ日時 2024-02-16 21:45:22
合計ジャッジ時間 29,152 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 691 ms
87,948 KB
testcase_01 AC 1,435 ms
100,704 KB
testcase_02 AC 1,713 ms
119,148 KB
testcase_03 AC 73 ms
73,724 KB
testcase_04 AC 47 ms
62,396 KB
testcase_05 AC 70 ms
73,596 KB
testcase_06 AC 951 ms
83,456 KB
testcase_07 AC 1,578 ms
122,160 KB
testcase_08 AC 1,481 ms
117,532 KB
testcase_09 AC 1,524 ms
122,840 KB
testcase_10 AC 1,723 ms
123,096 KB
testcase_11 AC 1,704 ms
122,840 KB
testcase_12 AC 1,767 ms
122,840 KB
testcase_13 AC 1,742 ms
123,096 KB
testcase_14 AC 1,756 ms
122,968 KB
testcase_15 AC 1,430 ms
79,272 KB
testcase_16 AC 1,461 ms
79,384 KB
testcase_17 AC 1,501 ms
79,268 KB
testcase_18 AC 988 ms
90,576 KB
testcase_19 AC 1,248 ms
112,700 KB
testcase_20 AC 1,257 ms
106,580 KB
testcase_21 AC 1,262 ms
122,584 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