結果

問題 No.3810 Binary Shortest Path Query
コンテスト
ユーザー tyawanmusi
提出日時 2026-10-01 19:24:59
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 368 ms / 2,000 ms
+ 164µs
コード長 3,166 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 982 ms
コンパイル使用メモリ 64,568 KB
実行使用メモリ 97,764 KB
最終ジャッジ日時 2026-11-20 20:52:34
合計ジャッジ時間 13,841 ms
ジャッジサーバーID
(参考情報)
judge3_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

def warshall_floyd(n, edges, inf=float("inf")):
    assert n >= 0
    dist = [[inf] * n for _ in range(n)]
    for v in range(n):
        dist[v][v] = 0
    for u, v, w in edges:
        assert 0 <= u < n and 0 <= v < n
        if w < dist[u][v]:
            dist[u][v] = w

    for k in range(n):
        dk = dist[k]
        for i in range(n):
            dik = dist[i][k]
            if dik == inf:
                continue
            di = dist[i]
            for j in range(n):
                dkj = dk[j]
                if dkj == inf:
                    continue
                nd = dik + dkj
                if nd < di[j]:
                    di[j] = nd
    return dist


# log(2)2e18 < 61
# 61 <= i 以降の辺は絶対いらない 誤読?
# 頂点0=ワープ空間
# i <= 60 の辺で考慮する頂点は 120 個以下 ワーシャルフロイドが回せるね
# Wi = 0 の時は頂点同一視

import sys
input = lambda: sys.stdin.readline().rstrip()

n, m, q = map(int, input().split())
s = [0] + list(map(int, input().split()))
edges_input = [tuple(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n + 1)
for u, v, w in edges_input:
    if w == 0:
        uf.union(u, v)
for i in range(1, n + 1):
    s[uf.find(i)] = min(s[i], s[uf.find(i)])

edges = []
candidate = {0 : 0}
for i in range(1, m + 1):
    u, v, w = edges_input[i - 1]
    u = uf.find(u)
    v = uf.find(v)
    if u == v:
        continue
    if i <= 60:
        c = w * 2**i
        if c >= 2e18:
            continue
        edges.append((u, v, c))
        edges.append((v, u, c))
        if u not in candidate:
            candidate[u] = len(candidate)
        if v not in candidate:
            candidate[v] = len(candidate)
for u in candidate:
    if u == 0:
        continue
    edges.append((u, 0, s[u]))
    edges.append((0, u, s[u]))
# print(edges)
dist = warshall_floyd(len(candidate), [(candidate[u], candidate[v], w) for u, v, w in edges])
# for i in dist:
#     print(i)
# print(candidate)
for _ in range(q):
    a, b = map(int, input().split())
    a = uf.find(a)
    b = uf.find(b)
    if a == b:
        print(0)
    elif a not in candidate and b not in candidate:
        print(s[a] + s[b])
    elif a in candidate and b not in candidate:
        print(dist[candidate[a]][0] + s[b])
    elif a not in candidate and b in candidate:
        print(s[a] + dist[0][candidate[b]])
    else:
        print(dist[candidate[a]][candidate[b]])
0