結果

問題 No.2630 Colorful Vertices and Cheapest Paths
コンテスト
ユーザー hirayuu_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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

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