結果

問題 No.3810 Binary Shortest Path Query
コンテスト
ユーザー tyawanmusi
提出日時 2026-10-01 18:54:23
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,955 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 81 ms
コンパイル使用メモリ 64,384 KB
実行使用メモリ 90,616 KB
最終ジャッジ日時 2026-11-20 20:52:05
合計ジャッジ時間 9,818 ms
ジャッジサーバーID
(参考情報)
judge4_0 / judge3_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 22 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

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 個以下 ワーシャルフロイドが回せるね

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

n, m, q = map(int, input().split())
s = [0] + list(map(int, input().split()))
edges = []
candidate = {0 : 0}
for i in range(1, m + 1):
    u, v, w = map(int, input().split())
    if i <= 60:
        c = w * 2**i
        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 _ in range(q):
    a, b = map(int, input().split())
    if a not in candidate or 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