結果
問題 | No.2630 Colorful Vertices and Cheapest Paths |
ユーザー |
![]() |
提出日時 | 2024-02-16 22:08:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,554 ms / 2,500 ms |
コード長 | 1,204 bytes |
コンパイル時間 | 392 ms |
コンパイル使用メモリ | 82,592 KB |
実行使用メモリ | 123,988 KB |
最終ジャッジ日時 | 2024-09-28 20:26:40 |
合計ジャッジ時間 | 21,318 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
class unif: def __init__(self,n): self.pare=[-1]*n self.size=[1]*n def root(self,x): while self.pare[x]!=-1: x=self.pare[x] return x def unite(self,u,v): rootu=self.root(u) rootv=self.root(v) if rootu!=rootv: if self.size[rootu]>=self.size[rootv]: self.pare[rootv]=rootu self.size[rootu]+=self.size[rootv] else: self.pare[rootu]=rootv self.size[rootv]+=self.size[rootu] def same(self,s,t): return self.root(s)==self.root(t) N,M=map(int,input().split()) L=[] for i in range(M): a,b=map(int,input().split()) L.append((a-1,b-1)) C=list(map(int,input().split())) for i in range(N): C[i]-=1 W=list(map(int,input().split())) Q=int(input()) result=[10**15]*Q q=[] for _ in range(Q): u,v=map(int,input().split()) q.append((u-1,v-1)) for bit in range(1,2**10): cost=0 for k in range(10): if (bit>>k)&1: cost+=W[k] Z=unif(N) for i in range(M): a,b=L[i][:] if (bit>>C[a])&1 and (bit>>C[b])&1: Z.unite(a,b) for i in range(Q): u,v=q[i][:] if Z.same(u,v): result[i]=min(result[i],cost) for i in range(Q): if result[i]<10**14: print(result[i]) else: print(-1)