結果
問題 |
No.2630 Colorful Vertices and Cheapest Paths
|
ユーザー |
|
提出日時 | 2025-02-01 01:12:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,981 ms / 2,500 ms |
コード長 | 2,459 bytes |
コンパイル時間 | 419 ms |
コンパイル使用メモリ | 82,164 KB |
実行使用メモリ | 242,648 KB |
最終ジャッジ日時 | 2025-02-01 01:13:25 |
合計ジャッジ時間 | 28,526 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
# https://yukicoder.me/problems/no/2630 MAX_VALUE = 10 ** 18 class UnionFind: """ UnionFindの基本的な処理を実装したクラス """ def __init__(self, size): self.root = [i for i in range(size)] self.size = [1] * size def get_root(self, v): if v == self.root[v]: return v else: old_root = self.root[v] new_root = self.get_root(old_root) self.root[v] = new_root return new_root def merge(self, u, v): root_u = self.get_root(u) root_v = self.get_root(v) if root_u == root_v: return False if self.size[root_u] >= self.size[root_v]: self.size[root_u] += self.size[root_v] self.root[root_v] = root_u self.root[v] = root_u else: self.size[root_v] += self.size[root_u] self.root[root_u] = root_v self.root[u] = root_v return True def main(): N, M = map(int, input().split()) edges = [] for _ in range(M): a, b = map(int, input().split()) edges.append((a - 1 ,b - 1)) C = list(map(int, input().split())) W = list(map(int, input().split())) Q = int(input()) queries = [] for _ in range(Q): u, v = map(int, input().split()) queries.append((u - 1, v - 1)) MAX_C = 10 # コスト計算 costs = [0] * (2 ** MAX_C) for bit in range(2 ** MAX_C): x = 0 for c in range(MAX_C): if (1 << c) & bit > 0: x += W[c] costs[bit] = x # edgeにタグをつける new_edges = [] for a, b in edges: c_a = C[a] - 1 c_b = C[b] - 1 c = (1 << c_a) | (1 << c_b) new_edges.append((a, b, c)) # unionfind uf_list = [UnionFind(N) for _ in range(2 ** MAX_C)] for bit in range(2 ** MAX_C): uf = uf_list[bit] for a, b, c in new_edges: if c & bit == c: uf.merge(a, b) # クエリ計算 for u, v in queries: answer = MAX_VALUE for bit in range(2 ** MAX_C): uf = uf_list[bit] if uf.get_root(u) == uf.get_root(v): x = costs[bit] answer = min(answer, x) if answer == MAX_VALUE: print(-1) else: print(answer) if __name__ == "__main__": main()