結果
問題 |
No.2630 Colorful Vertices and Cheapest Paths
|
ユーザー |
![]() |
提出日時 | 2024-02-22 01:08:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,904 ms / 2,500 ms |
コード長 | 1,397 bytes |
コンパイル時間 | 266 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 125,092 KB |
最終ジャッジ日時 | 2024-09-29 04:23:47 |
合計ジャッジ時間 | 29,580 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
import sys input = sys.stdin.readline N,M=map(int,input().split()) EDGE=[] for i in range(M): a,b=map(int,input().split()) a-=1 b-=1 EDGE.append((a,b)) C=list(map(int,input().split())) for i in range(N): C[i]-=1 W=list(map(int,input().split())) Q=int(input()) Queries=[] for i in range(Q): a,b=map(int,input().split()) a-=1 b-=1 Queries.append((a,b)) # UnionFind def find(x): while Group[x] != x: x=Group[x] return x def Union(x,y): if find(x) != find(y): if Nodes[find(x)] < Nodes[find(y)]: Nodes[find(y)] += Nodes[find(x)] Nodes[find(x)] = 0 Group[find(x)] = find(y) else: Nodes[find(x)] += Nodes[find(y)] Nodes[find(y)] = 0 Group[find(y)] = find(x) ANS=[1<<62]*Q for i in range(1<<len(W)): score=0 for j in range(len(W)): if i & (1<<j) != 0: score+=W[j] Group = [i for i in range(N)] # グループ分け Nodes = [1]*(N) # 各グループのノードの数 for x,y in EDGE: if (i & (1<<C[x]))!= 0 and (i & (1<<C[y]))!= 0: Union(x,y) for j in range(Q): if find(Queries[j][0])==find(Queries[j][1]): ANS[j]=min(ANS[j],score) for j in range(Q): if ANS[j]>=(1<<60): print(-1) else: print(ANS[j])