結果

問題 No.3810 Binary Shortest Path Query
コンテスト
ユーザー masasu
提出日時 2026-11-20 23:22:53
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,335 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 89 ms
コンパイル使用メモリ 64,340 KB
実行使用メモリ 92,700 KB
最終ジャッジ日時 2026-11-20 23:23:04
合計ジャッジ時間 10,890 ms
ジャッジサーバーID
(参考情報)
judge2_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

def solve():
	N,M,Q = LI()
	S = [0] + LI()
	G = [[] for _ in range(N+1)]
	LIM = max(S)*2-1
	E = []
	for i in range(1, M+1):
		# w<<i <= LIM
		# 1<<i <= LIM/w
		u,v,w = LI()
		if i <= (LIM//w).bit_length()-1:
			E.append((u,v,w<<i))

	# 全点対最短経路
	V = set()
	for u,v,w in E:
		V.add(u)
		V.add(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:
		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()
		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