結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-10-01 19:04:23 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
MLE
不安定
|
| 実行時間 | - |
| コード長 | 2,122 bytes |
| 記録 | |
| コンパイル時間 | 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 |
ソースコード
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]])