結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-10-01 19:19:53 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 3,132 bytes |
| 記録 | |
| コンパイル時間 | 1,950 ms |
| コンパイル使用メモリ | 63,912 KB |
| 実行使用メモリ | 97,616 KB |
| 最終ジャッジ日時 | 2026-11-20 20:52:27 |
| 合計ジャッジ時間 | 11,232 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge4_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 WA * 2 |
ソースコード
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 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]])