結果
問題 | No.2630 Colorful Vertices and Cheapest Paths |
ユーザー | titia |
提出日時 | 2024-02-22 01:08:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,056 ms / 2,500 ms |
コード長 | 1,397 bytes |
コンパイル時間 | 506 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 124,676 KB |
最終ジャッジ日時 | 2024-02-22 01:08:36 |
合計ジャッジ時間 | 33,860 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge16 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 874 ms
82,444 KB |
testcase_01 | AC | 1,863 ms
101,848 KB |
testcase_02 | AC | 1,481 ms
109,756 KB |
testcase_03 | AC | 83 ms
76,160 KB |
testcase_04 | AC | 51 ms
64,464 KB |
testcase_05 | AC | 82 ms
75,936 KB |
testcase_06 | AC | 859 ms
79,980 KB |
testcase_07 | AC | 1,773 ms
118,672 KB |
testcase_08 | AC | 1,544 ms
111,904 KB |
testcase_09 | AC | 1,765 ms
120,016 KB |
testcase_10 | AC | 1,890 ms
124,316 KB |
testcase_11 | AC | 1,914 ms
122,988 KB |
testcase_12 | AC | 1,903 ms
124,676 KB |
testcase_13 | AC | 1,895 ms
124,548 KB |
testcase_14 | AC | 1,888 ms
123,048 KB |
testcase_15 | AC | 2,035 ms
79,156 KB |
testcase_16 | AC | 2,034 ms
78,904 KB |
testcase_17 | AC | 2,056 ms
78,904 KB |
testcase_18 | AC | 1,035 ms
85,632 KB |
testcase_19 | AC | 1,289 ms
102,976 KB |
testcase_20 | AC | 965 ms
91,596 KB |
testcase_21 | AC | 1,620 ms
118,196 KB |
ソースコード
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])