結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
sepa38
|
| 提出日時 | 2026-11-18 15:26:54 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 2,493 bytes |
| 記録 | |
| コンパイル時間 | 89 ms |
| コンパイル使用メモリ | 64,092 KB |
| 実行使用メモリ | 187,784 KB |
| 最終ジャッジ日時 | 2026-11-20 20:54:52 |
| 合計ジャッジ時間 | 12,362 ms |
|
ジャッジサーバーID (参考情報) |
judge3_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 26 WA * 4 |
ソースコード
# 誤解法6: C++ で `long long c = W * (1LL << i);` がオーバーフローする実装を模倣(i<=62 で計算し、0<=c<=2e18 なら採用)
# - 答え <= S_a + S_b <= 2e18 なので、コスト > 2e18 の辺は不要(W>=1 かつ i>=61 は全部不要)
# - W=0 の辺は Union-Find で縮約
# - 残る辺は高々 60 本 → 縮約後の頂点 120 個以下で Floyd–Warshall
# - ワープは高々 1 回で十分。f(v) = min_x (d(v,x) + S_x) として ans = min(d(a,b), f(a)+f(b))
import sys
def solve(inp):
d = inp.split(); p = 0
N, M, Q = int(d[0]), int(d[1]), int(d[2]); p = 3
S = [int(x) for x in d[p:p+N]]; p += N
LIMIT = 2 * 10**18
INF = float('inf')
par = list(range(N))
def find(x):
while par[x] != x:
par[x] = par[par[x]]; x = par[x]
return x
small = []
for i in range(1, M+1):
u, v, w = int(d[p])-1, int(d[p+1])-1, int(d[p+2]); p += 3
if w == 0:
a, b = find(u), find(v)
if a != b: par[a] = b
elif i <= 62:
c = (w << i) & ((1 << 64) - 1)
if c >= 1 << 63: c -= 1 << 64
if 0 <= c <= LIMIT: small.append((u, v, c))
minS = {}
for v in range(N):
r = find(v)
minS[r] = min(minS.get(r, S[v]), S[v])
idx = {}
es = []
for u, v, c in small:
ru, rv = find(u), find(v)
if ru == rv: continue
for r in (ru, rv):
if r not in idx: idx[r] = len(idx)
es.append((idx[ru], idx[rv], c))
K = len(idx)
D = [[INF]*K for _ in range(K)]
for k in range(K): D[k][k] = 0
for a, b, c in es:
if c < D[a][b]: D[a][b] = D[b][a] = c
for k in range(K):
Dk = D[k]
for i in range(K):
dik = D[i][k]
if dik == INF: continue
Di = D[i]
for j in range(K):
if dik + Dk[j] < Di[j]: Di[j] = dik + Dk[j]
rev = [None]*K
for r, k in idx.items(): rev[k] = r
f = dict(minS)
for k in range(K):
f[rev[k]] = min(D[k][j] + minS[rev[j]] for j in range(K))
out = []
for _ in range(Q):
a, b = int(d[p])-1, int(d[p+1])-1; p += 2
ra, rb = find(a), find(b)
if ra == rb:
out.append(0); continue
dd = D[idx[ra]][idx[rb]] if ra in idx and rb in idx else INF
out.append(min(dd, f[ra] + f[rb]))
return "\n".join(map(str, out)) + "\n"
if __name__ == "__main__":
sys.stdout.write(solve(sys.stdin.read()))
sepa38