結果

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

ソースコード

diff #
raw source code

# 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()
	G = [[] for _ in range(N+1)]
	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[a], S[b])
		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]] = w
		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()
0