結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-20 23:48:01 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 348 ms / 2,000 ms |
| + 932µs | |
| コード長 | 2,838 bytes |
| 記録 | |
| コンパイル時間 | 1,731 ms |
| コンパイル使用メモリ | 64,056 KB |
| 実行使用メモリ | 91,284 KB |
| 最終ジャッジ日時 | 2026-11-20 23:48:17 |
| 合計ジャッジ時間 | 13,454 ms |
|
ジャッジサーバーID (参考情報) |
judge5_0 / judge3_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
ソースコード
# https://github.com/robe2222555/atcoder-lib/blob/main/template/python/main.py
import sys
input = lambda: sys.stdin.readline().rstrip()
def LI(): return list(map(int, input().split()))
def II(): return int(input())
INF = 1<<60
# https://github.com/robe2222555/atcoder-lib/blob/main/1_データ構造/UnionFind.py
class UnionFind():
def __init__(self, n):
"0-base index"
self.n = n
self.par = list(range(n))
self.rank = [0]*n
self.group_num = n
self.sz = [1]*n
def find(self, x):
"ノードxが属する集合の根を求める"
if self.par[x] == x:
return x
else:
self.par[x] = self.find(self.par[x])
return self.par[x]
def unite(self, x, y):
"xとyの属する集合を併合"
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.rank[x] < self.rank[y]:
self.par[x] = y
self.sz[y] += self.sz[x]
else:
self.par[y] = x
self.sz[x] += self.sz[y]
if self.rank[x] == self.rank[y]:
self.rank[x] += 1
self.group_num-=1
def same(self, x, y):
"xとyが同じ集合に属するか否か"
return self.find(x) == self.find(y)
def size(self, x):
"頂点 x と同じ連結成分の頂点の個数"
return self.sz[self.find(x)]
def groups(self, is_1_indexed = True) -> list:
root_buf = [self.find(i) for i in range(self.n)]
res = [[] for _ in range(self.n)]
for i in range(int(is_1_indexed), self.n):
res[root_buf[i]].append(i)
return list(filter(lambda r: r, res))
def solve():
N,M,Q = LI()
S = [0] + LI()
LIM = max(S)*2-1
E = []
UF = UnionFind(N+1)
for i in range(1, M+1):
u,v,w = LI()
if w==0:
UF.unite(u,v)
r = UF.find(u)
S[r] = min(S[r], S[u], S[v])
elif i <= (LIM//w).bit_length()-1:
# w<<i <= LIM
# 1<<i <= LIM/w
E.append((u,v,w<<i))
# 全点対最短経路
V = set()
for u,v,w in E:
V.add(UF.find(u))
V.add(UF.find(v))
V = list(V)
K = len(V)
compress = {V[i]:i for i in range(K)}
assert len(V)<200
dis = [[INF]*K for _ in range(K)]
for i in range(K):
dis[i][i] = 0
for u,v,w in E:
u = UF.find(u)
v = UF.find(v)
dis[compress[u]][compress[v]] = min(dis[compress[u]][compress[v]], w)
dis[compress[v]][compress[u]] = min(dis[compress[v]][compress[u]], w)
for k in range(K):
for u in range(K):
for v in range(K):
dis[u][v] = min(dis[u][v], dis[u][k] + dis[k][v])
for _ in range(Q):
a,b = LI()
a = UF.find(a)
b = UF.find(b)
if a==b:
print(0)
continue
ans = S[a] + S[b]
if (a in V) and (b in V):
ans = min(ans, dis[compress[a]][compress[b]])
if a in V:
for i in range(K):
ans = min(ans, dis[compress[a]][i] + S[V[i]] + S[b])
if b in V:
for i in range(K):
ans = min(ans, S[a] + S[V[i]] + dis[i][compress[b]])
print(ans)
return
def main():
T = 1
for _ in range(T):
solve()
return
if __name__ == '__main__':
main()