結果

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

ソースコード

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

# 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 = []
candidate = {0 : 0}
for i in range(1, m + 1):
    u, v, w = map(int, input().split())
    if i <= 60 or w == 0:
        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())
    if 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